I did some research after my government decided that the providers have one year the time to change their infrastructure so they can log following things:
- which websites you visit
- when you visit them
- who you mailed
- when you mailed
- from who you got a mail
- which hardware you used
- where you used it (when you get a call on your mobile phone, they will log the location)
- who you called
- who called you
- length of the conversation
- they log calls from landlines, mobile phones and services like skype
All these logs can be viewed by the government, police, even the institute for post and telecommunication,...
And they work together with the NSA, so I guess they will happily share everything with them too.
So in my search for a good mail provider I ended up with these 2:
www.countermail.comriseup.net
The first one you can pay with bitcoins, and the second one accepts Bitcoin donations.
But like some pointed out, you can't be 100% sure that your privacy is safe.
But imo better try than just give it to them.