Every wireless network management interface I've ever dealt with has allowed me to enter the actual key (in hex) without requiring the English passphrase. This is going to be your best bet.
You seem to already be aware (given your "Things I Realize" #1) that there is not a one-to-one mapping of WEP keys to English passphrases. The reason for this is that the key is a non-reversible hash of the passphrase. That being the case, unless there's a major flaw in the hashing algorithm (highly unlikely, given that I've never heard that listed among the litany of WEP's weaknesses), it is mathematically impossible to reverse the hash.
Since you can't compute the passphrase from the key, there are only two possible ways to do the conversion you're asking for:
1) Google the key and see whether it appears in any public WEP key rainbow tables. However, given that there's extremely little actual value to an attacker in converting a WEP key back into a passphrase (they can just use the key directly, so why bother?), I would be mildly surprised if any such tables even exist.
2) Generate a crapload of candidate passphrases and throw them at WEP's hashing algorithm and hope that one of them generates the desired key. While this will (eventually) work, it's almost certain to take longer than generating a new key and updating all affected devices unless you can remember enough of the previous passphrase to allow you to narrow the search space considerably.