From what you describe, it certainly sounds like Orange. I had that a lot with Orange in the very early days and with 3 in 2003. The only thing that would make me hesitant is the timeframe. Both Orange and 3 cells used to disappear for 5 mins to 10 mins max. (I assume they were rebooting).

Indeed, I once saw a cell that spent 3 days ping-ponging - spending no more than 5 minutes in each state. Bloody annoying, because there was another cell within range and the network had an issue with call-grabbing (the call would drop as it was handed over).

I'd try to talk my way through to engineering (use words like escallate and duty manager, but be very polite and helpful - above all don't suggest it is the network that is at fault until you are talking to an engineer). Older 'phones can be convinced that they belong to an Orange Engineer - thus getting access to the cells' unique identifier. I don't think you can do this with the newer ones (on 3, the Engineers have a little Java app, which is loaded onto the 'phone via a USB connection).

Actually, a quick search on Google suggests another possibility for hardware engineers with a sacrificial 'phone. Type "nokia codes tips" or "nokia network monitor" then hit the "I'm feeling lucky" button.