Are people just not receiving the registration emails, or are they not receiving other emails as well, i.e. when PMs are delivered, updates to threads, etc.? Also, is it just for some people, or is nobody at all receiving the mails?
You're hosted with ColoCrossing (or one of their resellers) and they are infamous for being on spam blacklists and harboring spammers. In fact, they were one of the top in the world at one point. Even though they cleaned up their act considerably, many providers still blacklist their entire IP address space. As far as blacklists are concerned, your IP address is currently on several blacklists. Could be the issue as well, assuming everything is working on the server. Have you checked your exim/mail logs (if you have access) to see what's going on?