How to prevent egg muffins sticking to non-stick muffin pan?
Non stick only goes so far, and eggs are some of the stickiest ingredients you can have. My advice would be if you can to heat the pans up first before spraying with oil and adding eggs, that way the egg won't adhere. If that's not an option then use cake release or butter and flour the pans, spraying oil isn't good enough, you need more of a barrier. 

There's a related question on the site here.