merolhack, check that the MTA on the server works, that it's configured correctly, the logs, etc.
That being said, I highly recommend this plugin:
http://www.shiftthis.net/wordpress-swift-smtp-plugin/
It allows you to use things like gmail.com for sending WPMU mail. The reason this is so vital is that my mail setup is just fine, everything works as it should, except that GMail will put WPMU mail in the "spam" folder (it delivers, just doesn't put it in the "Inbox") and Hotmail didn't deliver mail at all. There's a way higher chance that your mail will get through spamfilters and such if you're using a SMTP account at some major ISP or well-known mailservice.