Meant to post this earlier, but my Fiancefiancé actually came up with the perfect idea: Dog Socksdog socks.
- Protects the car - Insideinside and Outout.
- Don't have to worry about them falling off or getting blown away (Likelike with some of the magnetic options I've seen).
- (edit: we We have lost a few socks..., so either use socks that can be lost without issue or use something to hold them on - as per the top set of socks pictured below).
- Travel in style (when added to proper harnass, doggles and other assorted gear).
(source: petmountain.com)