You’re not doing anything wrong, this is just how probability works. Similar to how, if you flip a coin, you’re not guaranteed to get a heads if you flip it twice, even though it’s a 1/2 chance. Shiny hunting works the same way (although this would be more like rolling a 512-sided die). Even with the best odds, you may still need to hatch thousands of eggs before getting a shiny, or you might get it in less than 10.
I will say that going over 1000 for a 1/512 hunt is rare, so if you want to hunt more shinies, you’ll probably get it much earlier than that next time. And no, changing out the parents is unnecessary and doesn’t impact your odds in any way.