Certainly not Orange, sending SMS doesn't work AGAIN!! Even if it's a temporary problem it sucks big time. And in case there is no 3G available, there is NO Edge. I'd recommend A1 if you are in Austria!
There is no pan-European carrier, you pay roaming rates once you leave the UK.
The best 3G coverage is probably Orange (www.orange.co.uk) or 3 (www.three.co.uk). When out of 3G coverage on 3 you will roam onto Orange's 2G network. O2 (www.o2.co.uk) has probably the worst 3G coverage although it and Vodafone (www.vodafone.co.uk) will be sharing cell sites soon so coverage should improve. T-Mobile (www.tmobile.co.uk) and 3 also share 3G cell sites (not all sites yet I believe) to add to the complexities.
Find a postcode in Lakenheath, you can then use the coverage checker on each site.