Like nmerriwether said: Exim can be built with Perl embedded - you can expect some loss of performance, but check it out anyway.
Maybe you already knew that about Exim, and your requirements are of a different nature. Supposing so, I'll get long-winded:
Will your perl code be used as an MDA (delivering mail to the message store), or an MUA (composing and sending messages to the MTA, hopefully via SMTP)? Both?
If your MTA is going to be bombarding your perl script(s) with messages which need to be delivered to the message store, the choices drop away quickly. This is mainly because spammers sometimes try to deliver alot of messages to alot of accounts (most of which don't exist) at one of the domains you're hosting. Even daemonized, your perl MDA code will consume resources erratically and excessively -- invoking or forking to try to deliver each message -- as soon as the rate of delivery starts erratically becoming excessive.
You might then alter the MTA config to allow fewer simultaneous connections, throttle bandwidth, maximum messages from each IP, etc.... the result is that the perl MDA is no longer consuming all the resources, but overall delivery is slower and you start to get a nasty rash of support calls from users who suddenly can't get their 'zine out to their peeps.
Postfix (easy), Sendmail (big book), qmail (holier than you), and Exim (no relation to the skin disease) each have strong points. However, only Exim can save you in the above scenario, because of the mysql support. You can configure Exim to check the MySQL database (because that's where you put the user account data, for recoverability and extensibility reasons when creating your MDA) to verify the legitimacy of the destination address to which each message is being sent, and drop the spammers' connections at the RCPT TO:, before delivery is attempted by your perl. Thus the bullet of perl's overhead is dodged.
Of course, since Exim can deliver to maildir, you probably aren't writing an MDA in perl... nonetheless, Exim's routers configuration possibilities make it flexible -- like perl -- and it's developed by people wishing to make an MTA which does what sendmail is supposed to do. ;-) Also, with Exim you can integrate SpamAssassin -- the Bayesian filters are pretty slick.
I agree with some of the other replies that most people, if they're composing and sending email with perl, use SMTP so that it can work with any MTA (unless you already wanted to limit yourself to a certain MTA), so the MUA discussion is moot.
If you're planning to create a lasting -- dare we say timeless? -- application, I'd suggest looking at the development teams behind the MTA's. Who's going to be with you for the long haul?
In my experience, Exim's flexibility and ease-of-configuration make it the right choice for the most common mailserver implementations, regardless of the scale. Exim also appears to be the only MTA which gives Perl consideration.