As I understand it, the prepending of "mail" to the recipient's domain name is more of a convention than a necessity. The important thing, as far as receiving mail is concerned, is that the sender's email provider is able to locate the recipient's provider's server.
From a DNS perspective, one way of organizing things is something like this:
domaina.com ---- (MX record) -----> mail.domain.com --- (A record) -----> IP address of domain.com's email server
Forum DOs and DON'Ts
Never assume that information you find using a search engine is up-to-date.