What circuit will allow reverse polarity and continue to work?
Sounds to me like you need an 'ideal' bridge rectifier. Fortunately, these are available from Linear Technology.

Check out LT4320:

http://www.linear.com/product/LT4320