Alternatives to Lavabit, with no physical ties to the United States?

Runbox is based in Norway and are very privacy oriented.

it looks countermail.com is a good alternative, has an interesting feature: Diskless web server and some other "unique features".

The USB Key feature got my attention:

"USB Key option If you purchase this option, your email account will become even more secure, because it will be impossible to login without your USB key inserted into the USB-port."

hosted in Germany, you might want to look at

www.posteo.de

Just remember that you'll have to use the .de ending, otherwise the BND will do what the NSA does in the US. At least they claim they only read non-.de mails, just like the NSA did…