Arduino duemilanove not working

With open circuit voltage of 21.5V tha would be a great idea.
Mouser sells a line of Recom DC/DC modules,
such as

I'd look into something like that.