Specifically modifying the video mode to all available options on the boot line one at a time. Different success for each server upon which we tried. Yes, try all possible values until you "get lucky".
I don't believe there's a problem with failsafe, in fact it's entirely possible that the failsafe performs the entire installation exactly as the regular installation, but with a different video mode (!) and kernel. I don't think it install the kernel it boots from, but you could certainly check. If so, then there's no actual difference in the final install. One way to check would be to find out what the video mode is for the failsafe boot line and use it for the non-failsafe ...
