Odd question but... Does it need to be a mobile or can it be a carphone?
Reason I ask is that, at best, a handset is going to be a Class IV device which IIRC will only ever have a maximum Tx power of 2 Watts. The point is that a GSM (well any cellular phone) device needs to reach a minimum of three cells, be that base stations, micro sites or whatever, it must reach 3 in order for the network to triangulate the position and make mathematical calculations as you move towards / away from cells, when you are out in the sticks a 2W transmitter is challenged and this isn't helped by the lesser number of cells in lesser populated areas. When (if) the triangulation of cells is calculated the minimum power negotiation from the cells (which based on a Class IV device the return can only reach a maximum of 2W!)
The easiest solution to this is a more powerful handset and that would take the form of a Class II device 8 Watt, namely a carphone, these devices will make it possible to reach the minimum number of cells where a less powerfull device can't, the cells can then negotiate the return at up to 8W.
There are other factors to consider such as dual / triple band infilling to get over coverage issues, this is something that a single band carphone cannot handle.
Sorry for the technical description!