iPhone 3GS - NO SERVICE

Hello friends!

First of all thank you to get some kind soul for lose your time helping me.
First I want to say I'm not a "noob" complete (I've had since the 2G iPhone and now I have a 4 ...
I follow the jailbreak/unlock scene)

I have a iPhone 3GS from a friend who was presented with his girlfriend
(and obviously her and he did not know anything .. and I'm trying to help them)

The iPhone 3GS is purchased in Brazil (Anatel has the logo above) and seems to me that is unlocked
(Well, I can activate it in iTunes with any chip). But no matter what chip i put in it
it is "NO SERVICE" / "SEARCHING" forever ...

technical Data
- IPhone 3GS 32GB (MC133BZ) (Serial Number 87006DTN3NR)
- Modem Firmware 05.13.04
- Is currently in version 5.1.1 (9B206)
- Both IMEI and ICCID are showing (I know that for security reasons I will not say here .. but they are appearing)
- I've tried putting chips CLARO , VIVO and TIM
- All functionality seems ok ... WIFI, buttons ... etc. ..
- In Setttings> Carriers> I've seen appear VIVO / CLARO / TIM (Depends on the chip always comes up ... )

- I can activate it in iTunes without any problem ...
- I've tried (and got) to jailbreak withredsnow 0.9.14b2 (in MAC) and install Ultrasnow and nothing ..
- I've tried (and got) update to iPad baseband for the iPhone and try to install Ultrasnow and nothing ...
- I returned to baseband 05.13.04 with redsnow and install Ultrasnow and nothing ...
- I've tried it on and off with the chip / no chip .... leave enough time etc ... and nothing ..

ALWAYS THE SAME PROBLEM "IN Serivce" / "SEARCHING" eternal ....

Someone please help me?

hugs and thank you in advance!