I actually had a debate with a friend about this when we had a N64 tournament a while ago. We're both on the older side now (late 20s) and are old enough to have played Mario 2 when it was being sold for NES.
After about ten minutes of discussion, we believe Birdo is a boy who wants to be a girl. The Mario 2 manual did come up, and we believe Nintendo uses the female pronouns in newer media because Birdo has decided to adhere to the female gender. This actually happens quite often with people who are unsure of their gender at some point and decide to live as the opposite gender. There have been cases in the news about this recently in which the family and friends of such a person would start using the opposite gender pronouns and identification. This, I believe, is what happened with Birdo.
Notice how Birdo has no bow in Mario 2. The later versions do have a bow (although I really can't remember if the Mario All Stars game on the SNES has a bow). This is, to me, equivalent to someone unsure about their gender eventually going to identification through clothing and the like. It reminds me of a case I heard on the news about a year or so ago where a boy from a western state (Colorado? Texas?) started to dress and look (i.e. long hair) like a girl. (This was the child who wasn't allowed to use the girls' bathroom, which led to a court case).
Someone mentioned eggs. The thing is, we don't really know much about Birdo's species, and if eggs are being shot out of what appears to be a nose, this definitely isn't the classic egg-laying creature we're used to. Perhaps they aren't really even eggs at all and only resemble them. In Mario 2, after all, you don't see them cracking open. Birdo was also in Mario RPG and I don't remember anything like that happening there either. They're more or less projectiles, and it could be more a means of self-defense than reproduction.
OK--I hope this post wasn't over-political or anything like that!!