Denver to LA. Left Denver at some ungodly o’clock in the a.m. Returned to Denver on a 5 p.m. flight (meaning that I actually got home around 9 p.m.).
The job was actually in Denver. It was just that the interview was in LA.
ETA: Got the job, but should have declined.
Schenectady to Ithaca, NY.
I actually would have liked working at Cornell, but the salary wasn’t enough for me to uproot myself. They even asked me back for a second interview, but I declined.
But the high point is that one of the interviewers had read my novel. 
Plus I hear that the cost of living is one of the highest in upstate (i.e. north of Poughkeepsie.) You must have taken that into consideration so I have to ask if that’s true, cause when my mom was looking for a place around there the prices were prohibitive for her but not that much more outrageous than a lot of other places seemed (this was a couple years ago, you see: I’d assume that housing in the Ithaca area probably hasn’t fallen as much as it has in other upstate cities, [but moreso than in the more rural areas.])
NE OH toAZ - got the job
AZ to Nashville, TN - didn’t get the job.
Expenses paid in both instances.
I interviewed for a job in Santa Clara, CA, when I was doing my residency at UF in Gainesville, FL. I didn’t get the job, but the highlight of the trip was a tour through the Winchester Mystery House.
I was living in Montreal when I interviewed for a job here in Maryland, near Baltimore. Got the job, and then had to wait almost 6 months for all my work visa mess to work itself out.
But it was worth it.
Houston, Texas to Harvey, Louisiana (basically New Orleans) for a 15 second interview, I (rudely) did not get the job and I was so pissed that he wasted my time that he had to call the Police and have me escorted off the property, apparently he was not interested in having his face rearranged (which I offered to do).
Unclviny
From Baghdad to Jakarta.
Buenos Aires to Aberdeen Scotland (14 hrs to London - 1 hr to abz), got the job but couldn’t reconcile the loss of cow, wine and sun with the gain of interesting job, wind, rain and grey so stayed put.
Good luck in Abu Dhabi - ever been there? It’s a lot less hectic than Dubai.
I’ve got an interview in Canberra on the 18/02. So that’s about 1100km.
Luckily the job’s actually in Adelaide, I’ve just got to go to head office for the interview. But they’re flying me out and back. And giving me some cabcharge vouchers, so I’ve just got to get a taxi booked there and back 
Good luck, I still preach the “Dextrin Principle” regularly at work (“keep throwing stuff at the wall until something sticks”).
Unclviny
Well, it must be around 10,500 miles. From the UK (call it from Manchester airport) to Australia (Melbourne).
Granted, I was already planning on moving to Australia, so it wasn’t just for a job interview, but we had a date, time and place set weeks before I left, so it might count.
I got asked to fly from Boston to Atlanta for a job interview with Delta (I think, it was a long time ago). So much time had passed since first applying for the job, though, that I’d already found something else and turned them down.
When I applied for my first job in Tokyo, I did about 3 500-mile round trips on my own dime.
Not for a job, but I flew 5500 miles for a doctor appointment.
I’ve never travelled for more than an hour, but my dad once flew from London to Zurich for the first interview and straight from there to Muscat, Oman for the second. Total distance travelled: 3,750 miles (one way).
Austin, Texas to Omaha, Nebraska
North Carolina to Bulgaria. Second place would be North Carolina to Walla Walla, Washington, which took almost as long.