I would also think that is the case, but the IMEI from the *# should be the one that the lock code works for, logically anyway.
Do you know anyone who has a t-mobile acct? They can call T-mobile, explain that they got the phone from (insert way they got phone) and that they want to use when they go overseas next month, T-mobile has to give the code to any current user, but it may take a few phone calls and they may require the phone being put on the persons acct. (it takes about 2 days to get the code, then you can take it off, and they never have to use it, since the phone info is on the sim card) That way you can get the code for the other IMEI too, without having to pay for it