Both my iPods are Windows formatted, as I didn't have a Mac when I got the both of them.
I would assume that it is possible to reformat the iPod using the Update software from Apple (I recall something about resetting EVERYTHING by using the iPod software).
But now, is it really worth the effort to change them from Windows to MAC, as I only connect them to my MAC. The Windows format runs on MAC, and it seems to be fine, but would I gain anything by reformatting to MAC format?
EDIT: And while we are in iPods ... why in the world did Apple decide to NOT build firewire support into the iPod Video units. What a waste