Wildcard Domains And Email

I'm working on the idea of an email wrapping/branding service.

I'd like someone to be able to send an email to the service structuring the email address like this:[url]

The part in italics is the real destination and the part in bold is the address of my server.

I'll then parse the real destination out of the email, wrap it in some stuff and send it on.

From what I've read I need to set up a wildcard MX record. I've tried that but the emails just don't seem to get there.

I'd value your thoughts on how to deal with this problem and what questions I should be asking.