There, unfortunately, isn't another way to factory unlock an iPhone without the IMEI.
Many people on here know were I'm employed and have much of my info for previous trades (and I would be willing to share those details with trustworthy people) if that helps build trust.
I'm not saying you would, as I really don't think you would, but I don't like to take chances like this anymore. If you could point me to a reliable source stating that this isn't possible, then I might reconsider. Also, the trust-building things you mentioned wouldn't hurt.
I don't have an official source but it's likely hard, if not impossible, to "create" a new/different IMEI number on an iPhone's Logic Board.
I understand your precautions and don't blame you for having them. I'll PM you for some more details about me.
Wtfvanity brings up a good point about AT&T doing it for free. The only reason I would want to unlock my phone would be to resell it when I renew my contract, so I may as well wait and do it for free.
One more question - Would I be able to verify the unlock on my phone, without attempting to switch to another network?
Don't quote me on this but last time I checked if your iPhone becomes unlocked, the next time you connect it to iTunes it will give you a message saying it has been unlocked that looks similar to this.
+1 . Remember to plug your iPhone into iTunes after you use the unlock service.