You forgot the second most important number in power supply design (how much current), but I would hit TI and linear tech to see who has something suitable for a buck converter at whatever current you need.
TIs 'webbench' tool will do almost all of the work for you.
as 5V is very much less then 12V, I dont see an issue with extending the operating range down to 12V so the hold up requirement goes away (and down to 8V or so should be doable).
Unless you need more then a few amps, this is trivial to solve.
73 Dan.