You already mentioned the toughest flaw there - the certification. A lot of districts won't even let you interview someone who isn't, so try and get that fixed as soon as you can!

Otherwise as long as it's stated that's why you left, this year I think you have a pretty good chance of getting a job if you have some flexibility. The number of job openings so far this year is insane. Apply for anything that looks interesting, and don't overlook small schools!

I would wager that most people who are looking for a job will find one this year. It's a mass exodus from the profession, retirements, or people looking for greener grass!