I think the animalian legendaries are really tough to breed in captivity which is why they are unable to breed in games. (just like many real life endangered species)
At first look, I consider Articuno and Moltres female, Zapdos male, Raikou and Entei male, Suicune can be either, Meloetta obviously female, Cobalion and Terrakion male, Virizion female, etc. Of course, the anime has shown that there are multiples of many legendary species, so if there are indeed more than one of a given legendary, then all bets are off. Then they either do have genders that people haven't found out yet, or maybe they're true hermaphrodites.
The Regis would always be genderless because they look like robotic lifeforms akin to Golurk, etc.