In der Fränkischen Schweiz und im Pegnitztal haben Vodafone und E-Plus oft beide Probleme. Wobei E-Plus nun doch in letzter Zeit ne Menge Basisstationen dazugebaut hat und die Funklöcher kleiner geworden sind. Dafür liegt E-Plus aber bei UMTS zurück.
Aber alles in allem würde ich dir fast raten bei o2 zu bleiben. Im o2 Netz ist die Sprachqualität schon in Ordnung, und wenns wirklich mal in unwegsames Gelände geht kannst du bei T-Mobile roamen. So schnell wird schon nicht alles gebarred werden.