How can you mitigate those challenges and make sure a bare-metal restore is successful?
There's a couple of things. The first thing I'm going to throw out there is virtualization, virtualization, and virtualization. This problem doesn't really exist in VMware, Hyper-V and Xen. There's a different set of problems; I'm not saying backup is easy in VMware land. It's not. But, the whole issue around dissimilar restores goes away because it's the same hypervisor everywhere. Also, there's built-in stuff to backup at the image level, so you can restore the entire VMDK and you are off and running.
Also, just play with the stuff. Try it out up front. Another important thing is to standardize. The more you can standardize on hardware the better. If you are one of these shops that just buys the latest, greatest, cheapest stuff and you expect it to work, that's the surefire way to make this problem very difficult.
Finally, if you go the imaging route you'll be a lot better off. You don't want to have to load the OS the old fashion way. That way you aren't really doing a restore you are just re-imaging the system.