What is the best way to redirect email to a Python script?
but I don't really think it is
  feasible to actually support all these
  emails account normally through a
  webmail program

I think that your base assumption here is incorrect. You see, most 'webmail' programs are just frontends (or clients) to the backend mail system (postfix etc). You will need to see how your webhost is set up. There is no reason why you can not create these accounts programmatically and then let them use a normal webmail interface like SquirrelMail or RoundCube. For instance, my webhost (bluehost) allows me 2500 email accounts - I am not sure how many yours allows - but I can upgrade to unlimited for a few extra dollars a month. I think that using the builtin email handling facility is a more robust way to go.
I'd like to provide a functionality for users of my website to get assigned an email address upon registration (such as firstname.lastname@mydomain.com) but I don't really think it is feasible to actually support all these emails account normally through a webmail program. I am also not sure if my webhost would be cool with it. What I'd really want is to be able to have a seamless integration of this email into the bigger system that the website is, as it is mostly going to be for intra-site messaging but we want to allow users to put actual email addresses. So what I would like to do instead is have a catch-all account under mydomain and have this email look at incoming mail, see who it was meant to be sent to, and add a message for the user in the system.
So, the questions are:
1) Is this the right approach? How expensive would it be to get a host that would allow me to just assign emails to at will to my domain? I am currently using WebFaction's shared hosting.
2) If it is an okay approach, what is the best way to route this catch all account to my python script? I have read about .forward but I am not very good at UNIX stuff. Once I figure that out, how would I get the script to be in the "Django environment" so I can use Django's model functionality to add the new messages to the user?
3) Is there anything Django can do to make this any easier?
4) Are there any tools in Python to help me parse the email address? How do they work?