I have been using the register plus plugin for a while now, and everything worked fine, except the verification emails were not being sent off.
I think i have identified the problem. The problem came in when i enabled the custom user and admin notification emails. As soon as i deactivated it, all the emails started coming through.
I hope this helps at least one person out there who is having the same problems.