i had a similar problem and just got a replacement 3G today...
when my iPhone would switch to EDGE from 3G, the transition would be smooth, no problems there. but when i got back into a 3G area my phone wouldn't switch back. this would happen everyday because i work right on the fringe where a 3G area meets an EDGE area. if i would try turning airplane mode on and then off to try and get it to see 3G, it would just endlessly search. if i tried to toggle the 3G switch, i'd get No Service. sometimes, after 30 minutes or more it would come back, but usually i would have to do a hard reset.
i tried all possible troubleshooting and nothing worked, so Apple swapped me out.