I called Bell. The phone was purchased from them, I have a copy of the receipt and has only been registered once with them. It was purchased in October. The ESN was clean - never reported lost or stolen. I purchased it off him a month ago and it worked until I replaced the battery at which point the "Service Required" message appeared. I then wiped the handset using the option under Security Settings, but still had the "Service Required" message. I then used JL_Cmder to wipe the entire handset and reinstalled the lastest OS. STill the message "Service Required" and the ESN is showing as 0's.
I didn't check the ESN prior to using JL_Cmder, so I can't confirm if it was showing as 0's prior to.