I'm trying to find a cell phone and cell provider with the best coverage in the UK, Germapy, and NYC area in America. While over seas, the phone needs to have local access and calls home; without costing a fortune. The phone needs to be a fancy data-enabled one (ie: Treo, Samsung i830, Blackberry, Nokia 9300?, or the many Windows Mobile models) with data access in DE and UK.

First thought was Cingular. After checking some coverage maps, T-Mobile looks like it has a strong presence in Germany, and I think it's a decent player in the US.

Any ideas for cellular voice/data access in UK and DE? Prepaid SIM cards (suggested by T-Mobile)? Prepaid data access??? Verizon's right out, eh? Thanks.