Would also be helpful if you can say which operator you are using. While Nokia Messaging is not a paid for service , there is a deal with the operator in there, hence why it checks for service availability (when you do see the menu item). It might be dependent on a 3G contract in specific countries.

When I set my N900 up (UK) it did disappear a couple of times. But a reboot seemed to bring it back.