Resolution!

I killed PhotoRec and went back to TestDisk. I let it run for 25% of the card, after which it found nothing. I told it to stop and then just told it to write out a FAT32 partition using the whole damn thing. Some scary error messages ignored, quit the program, pulled and reinserted the card, and voila! Problem solved.

So, it does indeed seem that the camera's "format" isn't very smart about partition tables. Now, the question is what I need to do, on the computer, to make sure the card continues to be "clean" for future shooting sessions.

*sigh*