Question

If you catch Sudoowoodo/red gyrodos, do they come back after e4/champ?

Answer 1

Sudowoodo: Only one. So if you catch one you can't catch one again.
Red Gyrados: Only one. You can't get it again unless you don't catch it.