Both of our kids have taken thousands of photos twice in Japan, once in the summer of 2008, then just a few weeks ago.
In 2008, they were loaded up with handfuls of 1 and 2gb cards, and numbered, and marked used.
This last trip, they used an 8GB card, then a few 2GB cards after that, keeping in order, and marking used.
When home, we backup to about 10 different computers/hard drives, but keep the cards around until some of the drives or media gets distributed around like moved onto multiple DVDs and shipped to other family members.
If you're using the same card in the same camera, a quick format should be fine with fat16, and fat32. If you're moving the card around, I'd agree that a full format in the target camera would be the most reliable.