I've got a solution just today. I had similar the same problem
--------------------------------------------------------------
"No Welcome Message". To fix this problem:
I. Start iPhone 4 with Gevey Sim + Your ordinary Sim card
II.As expected there is no message, so open your sim card slot
III. You don't need to wait for something and just plug it right back in
IV. The iPhone is going to search for services and connects to your provider with 1 status bar
V. Meanwhile the "Welcome Message" should put up
VI. Follow Install description
--------------------------------------------------------------
-------------------
My install strategy
-------------------
Steps I-V
Immediately after accepting the "Welcome Message"
Call 112 or 911 whithin 2 seconds then hang up the phone
After that go to settings => turn on, turn off airplane mode
Do this procedure til you're getting the status bar
It usually shows up with just 1 status bar
After a while you get full service
Note: If there are errors popping up like "sim error" or "no sim card installed" at the very begin plugin the sim card slot back in or even no service displaying, repeat step II-VI.
You don't need to wait between this steps, just call properly and repeat this if unlocking your sim lock isn't working.
--------------------------------------------------------------
Iphone 4 - 16GB - 4.3.3 - 4.10.01 - Gevey Turbo Sim