Hi Again,
sorry for the slow response but my original reply was through the listserver and it seems a bit slow at the moment.
12V at 5A is 60W, quite a lot of power. DC-DC converters at this level are not very common, Power-one (formerly Melcher) do a 50W (12V 4A output) unit with 8-15V input but it costs £180.
This power would be pushing the limits for a simple Buck-Boost (stepup-stepdown) solution using the National or Linear Technologies devices. You are looking at a full-blown transformer based design. What is the average current draw of the unit and the duty cycle of the high power operation, 60W is a lot for solar power! What charge regulator are you using for your batteries? For long life you do not want to discharge them much below 11.5V anyway, so perhaps you colud switch in a simple dropper (3 silicon diodes in series) when you are charging and short it out with a relay when off charge. A Pic would make a good control for this and you could use more than one relay. A 13V (I don't think your unit will die the instant you exceed 12.5V) shunt clamp / regulator across your load could take care of any transient events without consuming power during normal operation.

Regards,
Robert.