Well, here are the results of my exhaustive investigation.

1. "Search" doesn't seem to be able to find anything on the removable memory card. Period. Only the internal memory card, and the device's built-in memory. Seriously, try it yourself.

2. I was successfully able to search for the contents of plain text, and HTML files (as long as they weren't on the removable card). I was not able to search for the contents of PDF or RTF files (no hits).

3. Search "Files on Nokia N800" was sufficient. Search "All" takes an incredibly long time, and I actually gave up and canceled it because it seemed like it would never end. I think it's actually trying to find Bluetooth devices it's paired with and search those.

A couple of other humorous anecdotes:

1. Connecting the N800 to my Mac OS X desktop the first time only mounted the internal memory card. The second and subsequent times, both cards were mounted.

2. Ejecting the N800's cards causes them to immediately re-mount. You have to do this hilarious lunge to unplug the USB cable before they re-mount.

I hope someone else finds this information useful besides me.

EDIT: Oh, also, documents in subfolders were found successfully. They didn't have to be in the root of the card or anything silly like that.