I got the app Baby Story for my iPod Touch a while ago, and then decided I didn't like it and deleted it. Part of the reason I got rid of it was because it would pop up random messages with things like, "Your baby is hungary!" The app appears to be completely deleted, and I can't find any reference to it on the iPod anywhere, but I'll still get random notifications with things like, "Your baby is sick." Is there a way, short of reformatting the iPod, to stop these messages?
Removing an app should disable all of the Push Notifications. Try rebooting your iPod, and making sure that iTunes did not re-install it.
Also, you can try disabling all Notifications, then -re-enabling them.
Maybe post a screenshot of the message. You may have another app installed (mBox for example) that displays messages from apps that send emails as well. (of course this is just a far fetched scenario).