I am having the same issue now.

Battery ran out then phone switched off> Plugged in the charger> Removed the battery to turn the device on again> Connected to wi-fi.
"Poof" Nokia Messaging gone from list of service providers.
On t-mobile USA

Any ideas please?