Every time a wikimail has been sent via Special:Emailuser the recipient shall be notified via echo, too. Just say: user:A has sent an e-mail.

Rationale:

• Wikimail is used when public conversation is not appropriate; the communication shall be kept invisible.
• Even the fact that user:A is contacting user:B in this particular situation at this point of time might be confidential.
• Users often separate their e-mail account for wiki purposes from their regular traffic; e.g. since the address contains the real name and institutions, which should not become involved or tell a lot about the registered user.
• The mailbox for wiki stuff is not necessarily checked on a daily base. That might happen only if a reason comes to mind.
• The sender of a secret mail has no way to nudge the recipient than public advertising, perhaps on talk page or more sophisticated escapes like hiding in an edit summary.