Another way advertisers ruin a beautiful thing.
More and More Free apps are using them. I have add free and they still manage to get by it. Wouldn't be so bad on the developers part if some of them offered a pay version of their program that took them out.
Anyway the air push is just like your email getting pushed to you from the server not from the phone.
Ok to the OP
My guess is that rather you gave it your number or not it probably read the phones info and sent it to the server. I look for these to be more frequent in the future.
I don't mind paying for an app but if it offers a free version then let me try it out to make sure its going to work for my needs if it does great i'll pay you however if it doesn't let me remove all of it. Including the add push that you distributed with it.