Now that you've got it all in the archive, can you do a custom search only within your history?

You mean do a custom Google search only over URLs already in my Firefox URL history? I can't do that, no. (In part, because my current Firefox profile is only 2 years old or so.) I prefer going through Evernote, IRC logs, site searches, or just my local cache as you point out.

I think one could set it up if one really wanted to, though. Google offers Custom Search Engines to which you can upload target URLs in an XML file thing. >6k URLs blows the limit, but the CSEs let you specify pages where any URL on that page is then treated as a target, so you'd just dump your history onto a page and specify that.