This is not normal. Upon initially booting the phone and making your first internet connection with RIM, you get this generic Blackberry Registration message in your messages folder. What you can do to stop getting them is go under options>advanced options> host routing table> press Blackberry key> choose register now. On the new 6.0 OS the steps are options> device> advanced system settings> host routing table> press Blackberry key> choose register now. You will get a confirmation that your device has been registered on the Blackberry network (just like your other ones), but by doing it manually, it should clear the error. Pull the battery after receiving this confirmation message.
If you still receive the registration messages after following these steps, it could be a corrupted service book. PM me if the above steps do not work, and I will get the info to get that fixed using a BIS Admin tool I have for RIM (you can also do this through www.blackberry.com/go/vzw if you want to try it yourself).
Please follow up with us and let us know if that took care of your registration message.