One option not mentioned yet is Posteo. They don't keep your IP and strip it in case your mail client sets it in the headers. They also don't take any personal identification for signup or billing (you can even send them letters with money to pay for a mailbox).
I don't know what came of it, but they've been told by the German constitutional court that their approach ("we're using NAT, we don't know the IP on the actual server") doesn't fly and does not protect them from complying with a court order.
