I don't see a data file that stores address history, or transactions indexed by address for quick retrieval by address unless I'm mistaken.
That is mostly correct. If the address is in your wallet, all transactions related to that are stored in the wallet.
Otherwise, address history is not stored.
I expect it's not going to be too hard to store the transactions indexed by address. I may be wrong there. Maybe leveldb can be used again and keyed by address?
Yes. leveldb is a generic key/value database. You may store anything you like in there.