Hmm, your post seems to imply Firefox does searching of full text history page contents natively -- is this true? I'm trying (on nightly) and can't seem to trigger it.

If not natively, which add-on are you using?