Extremely large wallets take a very long time to load.
After some testing I found that most of the time was spent in EC_KEY_check_key
The fix this I have merged two of the checks into using a single CECKey instance, replaced EC_KEY_check_key with a faster operation (thanks to sipa for helping me there), and appended a hash of the private key to "key" entries.
On my system loading one private key took approximately 1500 usec.
CKey::Load reduced this to 900 usec replacing EC_KEY_check_key reduced this to 500 usec checking just the hash reduced this to 40 usec