Stop notifications from a deleted app
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).