I can imagine operating Lavabit-type of service in some European country. EU's grip on the internet is much weaker than that of the NSA, and recent efforts towards strengthening online privacy give me the reason to believe that it would be difficult to actually shut down such a service. Provisions for obtaining private data through a court order exist also in the EU so there is a legal way for the government to go after criminals who would use it, and with the recent revelations of how thoroughly has the EU been penetrated by NSA (literally as well as figuratively), spinning it as moving from the no-longer-free USA to the still-free EU would also help to protect the service - should anyone try to lay a heavy hand on the service, I think that it would quickly escalate into a discussion in the European Parliament and a lot of scathing titles in big newspapers. Other indications - for example how big are current EU research grant calls in ICT on online privacy, security and trust - also make me believe that Lavabit could work here. So don't hesitate, come here and be free again, guys ;)
Also, I don't think that the MU case is pertinent here, as it happened in a US colony.