Obstacles in job hunting for US citizens in non-US nations I am curious to know the kinds of obstacles a US citizen would come across when trying to find work in academia outside the US and/or those that a non-US-citizen faces when trying to get an academic job inside the US.  

It would seem that, logistically, it would be easier on the department to hire a citizen over a non-citizen. Is there any advice applicants can follow that would greater their chances?  Do you have to be extraordinary for a department to hire you over an equally qualified citizen?
There a multiple levels on which this problem operates. This is especially true for places saturated with immigrants. (For instance, USA with Indians/Chinese)


Getting the Job

This problem itself has a million subdivisions. Firstly, it is fairly difficult for immigrants (who studied in that country) to get jobs without exhibiting something really outstanding. The problem is not so bad for sectors such as computer science and electrical engineering wherein professionals are required by the dozen. The problem, however, is really bad in areas such as Theoretical Physics or Chemistry (or basic sciences). With limited vacancies and a million outstanding candidates, it is really difficult to crack that "top job".  
Working in Sensitive Sectors

I don't even want to get started on sectors like Aerospace. More often than not, graduates from the top universities in USA and Europe have returned to their homelands because all companies stress on citizenship. For EU, it is fairly difficult for a Non-EU resident to get a job in the first place, add to that defense and secrecy and you have a useless degree. In USA, it's even better, if you graduate with a PhD in Aerospace Control Systems from say, Stanford, you are still worthless for US companies because they don't ask just for citizenship anymore but also Top Secret (or Lower) Security Clearance! That's at least 10 years for a foreign citizen.
Immigration and Visa

Getting a job is one part, getting the necessary immigration documents cleared is another. I mentioned about Aerospace engineering being a potential problem as far as jobs are concerned. But thats not all! USA has published a list called the technology alert list which requires screening of candidates before granting a visa. 

The immigration laws in the Europe aren't very friendly for Non-European to begin with but as far as I know, they don't maintain a strict segregation between "things non-citizens can't do" and "things they can". However, rising far-right politics, things don't seem to get any better in the future.