Who would Huckabee pick? The ideal candidate would be a solid fiscal conservative with foreign policy credentials who isn't from the South or the Bush Administration.
Well, I still think Hutchison makes the most sense, and also (in response to Pim Fortuyn) I don't think his running mate would *have* to be someone who's under 60. I don't see why mid-60s is necessarily too old.
However, one slightly unconventional choice who might be interesting, who's under 60, continues the GOP trend of VP candidates who've never been a governor or senator, and meets most of the criteria you mention above is SEC Chairman (and former Rep. from California) Chris Cox.
Served in the House for 16 years, much of that time in the leadership, was involved in a lot of legislation on economics, but also has a bit of national security experience, in that he spent some time as chairman of the House Committee on Homeland Security and chairman of the Select Committee on US National Security.