More thinking out loud:

If there are only a few thousand entries then loading the whole thing into memory is pretty low cost. If you first scan for old keys that contain wild cards you are likely to end up with a manageable group of keys that you can then test one at a time against the search key. One way to do that is to turn the test old key into a regular expression and test for a match against the search key.

Let me know if you want to see some sample code.