I jailbroke and unlocked my 3GS (4.1, baseband 06.15.00) a few months ago to use it in another country. However, my 2-year German contract is up and I could ask my former carrier to ask Apple for the official unlock. Would this work on a jailbroken/unlocked phone? I want to upgrade to IOS 5 without needed to jailbreak to unlock the phone again (I don't use jailbroken apps, really, just used it for the unlock).
You'll need to restore the firmware using one of the jailbreak applications. Pwnagetool, redSn0w, etc.
The reason is the 6.15 firmware is from the iPad and it's version is higher than what is in the normal 3GS firmware. iTunes will see this phone is different than what it expects and throw an error (1015, I believe).
As the unlock developers have stressed, repeatedly, the custom 6.15 firmware is a one way deal. Once you do this you can't go back to the normal firmware anymore. To update in the future you'll have to continue creating custom firmwares, the factory firmware simply won't work anymore.
Return your phone to its standard state, so ios4.1 and then yes, you can ask the carrier to request unlock from Apple.
The unlock works by changing a database entry for your UDID on Apple servers and therefore whether or not it's jailbroken should make little difference. With that said, to be sure it's all worked ( and because you are planning to) taking it back to a standard OS install would make sense.
Hope this helps.