Why does their server need your private key? (Except "paranoid" level - I'm much more concerned about handing my private key over to them than anything to with email, why's that paranoid?!)
Why can't they just receive, encrypt with my public key, let my client decrypt with private?