I am having the exact same problem as Speedline and I have also carried out similar exercises except for the fact that the instructions were actually given by the carrier's tech support.
They got me to remove and replace the battery for about 50 times in three days. Finally they booked it as an official complaint. Which probably means nothing's gonna happen now considering who my carrier is.
Worst is before I deleted the service books, I could atleast send and recieve the mails, message on bb messenger and browse net when I was in WiFi coverage. Then they asked to delete
all books
and since I am not receiving any service books, the phone is pretty much just a phone.