Err, I’m going to have to disagree here. I found my first job in Florida while living and going to college in Pennsylvania (OK, this was a big company that recruits at my college).
I also found my current job in NJ while living and working in Florida. This is a job with a small company that was only considering local candidates. The trick is to put down an address on the initial application that is local to the area you are looking in (perhaps the address of a family member or close friend). Once I made it past the initial screening (monster allows employers to filter on home address), I explained my situation, and flew up on my own dime for the interview. I also paid all my own relocation expenses once I got the job.
Now, this was my third interview, after nearly two years of searching on and off. If you are not going to fly out to visit family or friends anyway, then making a special trip just to do an interview can get rather expensive, I will admit. It is also much harder to network long distance like this.
As to the OP, often business travel does not go between corporate offices of a single company. I mean, if the company had a local office, why wouldn’t they just use/hire local personnel for the task, unless it is just a one time deal? It doesn’t really make sense to pay to fly someone back and forth constantly. I would start off by calling Lucent, Sprint, and Southwest, and asking them how many employees they have that actually travel back and forth on a regular basis between those two sites. I would guess it’s a few VP’s and maybe a regional manager or two at most.
One more tip: unadvertised positions are usually filled via referral, and not out of the huge pile of unsolicited resumes. But it’s never too early to start networking. Good luck!