For that number of addresses you really need a full-node client. (Armory or Core)
If you don't, then querying the lite-wallet servers will probably get you soft-banned from querying them (they'll view you as DOSing them)
I would use Core and write a script that will run the following RPC call for each private key
importprivkey <privatekey> "" False
(The private keys should be in WIF format and without the <> or any "" around them...)
The [ "" False ] part is a must. only remove that false (or change it to True) on the LAST private key you import...
If you don't, it will rescan the blockchain after every import and take a REAAAAALLLY long time, if it doesn't crash.
Maybe Armory has a better solution, but afaik bitcoind would be the best way to go.
I'd tend to agree with using Bitcoin Core, even though it looks like that's what you were using when the problem occurred. Bitcoin Core uses Berkeley DB as its wallet.dat format. Berkeley DB is a bit bloated, but it's mature, very scalable, and has some reasonably decent recovery tools. I'm not aware of any other client that would be equally scalable (not that I'm an expert on alternative clients though...).
As much as I like Armory, I don't think it would scale as well (although it's wallet format is nice and simple and more error-resistant than any other wallet format I'm aware of).
For importing, as an alternative you could use the RPC command:
The wallet import format is a bunch of lines like so:
Kx2GEDGhepMhkUnymSFtrU2Q59KMPY75oYjBVofYV9032p5L4a2b 2014-06-19T00:58:01Z change=1 reserve=1 label=label%20with%20spaces
The first two fields are required. If you don't have the address creation time, you can replace that field with something meaningless (e.g. "DATE-UNKNOWN") but something needs to be there. The last three fields are each optional. Only a single rescan is done at the end of the file import, and if you do have
all of the creation times, the rescan will intelligently start at the right time instead of starting at the genesis block.