Safe email and messenger advice?

Is having truly private (non government watched) email or messenger service remotely possible? Any advice?

I think a good solution for you needs would be
Hushmail (encryted + high anonymity)
a lot folks from the "Warez-Community" also uses this service very often
Hushmail FAQ

i hope this helps.
btw: its FREE

Get yourself setup with a good solid email client and use something like GnuPG to encrypt your email messages, there is no assurance that its uncrackable but its better than leaving all the work to someone like Hushmail who may or may not be cooperating with govermnet authorities. Also do keep in mind that the headers such as the subject line of the email is sent plain text so even with the main message encrypted and encrypted attachments some information can be gleaned from the headers.

Also the multi-protocol client Gaim supports message encryption via GnuPG plugins for MSN and probably other services if you look around enough. Of course then you have to worry about things such as TEMPEST, physical keyloggers, and other more direct methods of snooping.

The bottom line is that if its on the internet its not completely safe, but it certainly is possible to make it difficult for your average scriptkiddie to pick up on what your talking about, but when it comes to goverments just think about this; there are billions of dollars in the black budgets, so be weary of underestimating the black hole.