I've started getting these as well. For a couple weeks now. One was telling me my phone was too slow, a couple telling me my battery was low (phone was fully charged!) and the latest was to meet singles in my area. I've gone to the last two and marked the apps as spam in the market. None of these are things I've got installed on my phone. The only apps I can think of that might be linked to this are TapFish and Words with Friends. I'm deleting apps I don't use and going to try and keep an eye on the notifications to see if I can figure out what is causing it for sure. If I find anything I'll update.
Also one-starring the apps that show up won't work since it looks like the only way to do that is by actually installing the app.
*update: I found AirPush Detector for free on the market. It's by Dan Bjorge. He's not connected to Airpush and it found an app that's using it--not the ones I mentioned above. If anyone has Blogger-Droid that's one culprit!