Vodafone is usually OK for me. The travel survey work I do takes me to some quite remote locations (quite literally in the middle of a field at times, if part of the National Cycle Network passes through it) and some really well-populated areas, such as Islington. I can't recall ever being unable to get a signal when I'm working. (The only places where I sometimes have a problem are right on the coast, where the cliffs might be locking a signal).
Remember though that some phones have far better (or poorer) 'sensitivities' to weak signals than others, so it might be your phone (rather than your network provider) that's the real cause of the problem.
This might help:
http://ask.ofcom.org.uk/help/telephone/mobilecoverage