Have you worked with a service? I used southern teachers a few years ago (
http://www.southernteachers.com/) and they were really optimistic that they could find me work. I ended up taking a public school position before I went on any private interviews, but I think they would have found me something.
I was specifically looking for middle school math though, so maybe that's why they were so optimistic!