Some friends of mine have a Toshiba Tecra 9100. The RTC battery on that is tucked inside the case just near to the front, and not easy to get to. They had a very similar problem to yours, and as it was out of warrantee, they used a company in West Bromwich.
http://www.laptopsolutions.net
I *think* the repair cost about £150. The company arranged for courier to collect and return, and rang back with a price before commencing work. Not sure if this was value for money, other than the repair was guaranteed and their laptop has been okay for the few months since.