A friend of mine does Windows hosting and uses Merik(sp?) mailserver which seems to be pretty decent, its not free mind.
boiling it down to its parts you need a pc with a cpu (as opposed to those without one, they dont tend to work was well or as quickly), some ram, fair bit o'disk space, network card, operating system, mailserver software
personally I would recommend using a FreeBSD server with a mailserver on that, provided its not sendmail or exim (so preferably qMail, or LordOfLA would recommend Postfix) then it should be reasonably good.