I did a little research, it's not the fact that they DON'T have a gender, it's that the gender is unknown!
I mean Lugia has a baby in Pokemon, female Lugia
So, what genders would you give what Legendaries?
For me It'd go like this.
Mewtwo and Mew : Both, the new movie has a female Mewtwo, but the older movie has a male Mewtwo, and the fact that Mewtwo is a clone from Mew, wouldn't there need to be two to begin with?
The Legendary birds (Articuno, Moltres & Zapdos) : I'd say all 3 of them are female, I don't know, they just give off that Vibe of femininity.
Next comes the dogs, I'd say Suicune and Entei would be male, and Raiku would be female, although I can see Suicune as a female too, but something just tells me that it'd be a 75/25% ratio.
Lugia I'd say would be both, the anime shows that there is, indeed more than one legendary, whether or not it's a 50/50 chance however I'm unsure.
Ho-oh to me feels like a woman, or a fabulous man.
Celebi, female hands down, but again it could be both, the mystery dungeon games (if you count those as canon) show that there is more than one Celebi.
The Regis except Steel are all male, Steel gives me a womenly vibe, although I was talking with someone who thought Ice would be the female, opinions are nice c:
Rayquaza and Groudon to me feel Male, Kyogre feels female, just one of those things that just you just feel.
Latios & Latias, not much to say, we have a canon legendaries with a canon genders.
Jirachi, I'm not too sure, I get both female and male vibes from this Pokemon, so I suppose I give it a 50/50
Deoxys, it's Alien so it could be either.
And I'm going to halt my list here for the time being, I feel like I'm just dragging the same point over and over, but I'll reply in too with my other thoughts on this. Like the legendary Lake Gaurdians, they all feel female to me, even Azelf.