Your expenses don't seem that bad to me. Although I'm confused how you save $5000/month when your income is $4,000/m..
Is your only reason for moving lower COL? I don't think that is the best, single criteria to find a place you'll be happy. Higher COL means a higher income (and vice versa) and usually also a nicer area, better public services etc. I could live cheaper in a trailer in Appalachia, but there's no way I'm doing that.. Taking a 20% pay cut to live in a 20% cheaper area gets you nowhere (except probably to an area where the schools and buses are less well funded)
I'd suggest criteria higher on your list should be what you like to do (outdoors, city life) what kind of people you want to be around (political views etc), what kind of job and of course salary. Then consider COL. Now, if you have already considered all of these things then good on you, ignore all this.
To your question; I don't see how you'd have anything to loose by applying online from out of state then traveling for an interview. Then if that don't work then consider moving there.