The current implementation of gsmloc as on gsmloc.org uploads GPS locations along with cellid information, this leads to a large amount of data being stored. These are reduced to bounding boxes on the server.
The current implementation within WhereAmI uses a bounding box for each cellid that grows as you move around within that cell.
CellID's can probably move, so an ever growing bounding box is probably not the best.
How about storing four locations for each cellid along with the date that the cellid was seen at that location. The four locations will be stored as the locations that extended the bounding box in each of the four compass directions.
To reduce space for on device storage the locations can be reduced to 32bit quadtile values and the date to a 16bit number of days since say 2000 (works upto 2179).
We also need to pack all the parts of a cellid value into a 32bit hash value to make for easy searching.
Server side we need to store dated cellid locations, from which bboxes can be returned when mobile users request their location. The bboxes will be based on the most recent locations reported (maybe the last 20).