Was it locked with the passcode when they took it? If so, they are effectively locked out (no known exploit to get around the passcode lock). They can restore it in iTunes as new, but that removes all of your information, content and apps and sets it back to a new-device state. Since your carrier offers IMEI locking, they cannot activate it on that network, but unless your country and/or all the carriers in it offer a coordinated IMEI blocking service, they may be able to activate it on another carriers network, although they may have to hack it if it is carrier locked (or still sell it in another country, where your IMEI block has no effect).
Regardless, the passcode lock will have kept your information safe, as long as the screen was locked when they took it.
If the screen was not locked when the snatched it then they had a few minutes at least (you said 10 or so) to puruse your information, but you've covered yourself there anyway by chaning passwords and such already. If the device connects to the network long enough for it and the iCloud servers to establish communication, then your remote wipe would go through. Unless, of course, in those first ten minutes they were able to go in and simply delete your iCloud account - no iCloud account, no iCloud settings, thus no find-my-iPhone enabled (did you have restrictions enabled, and did you disable allowing changes to accounts by chance?).
You sound like you have done your best to cover your back and protect your informatin. Odds are they will already have restored the device as new, and either set it up on another network, or sold it off.