Some of our EMail problems of the last couple of months stemmed from our DNS server not having a Reverse DNS zone configured.
A lot of the new rules that most providers are using to ensure no spam reaches their servers is to immediately block messages from servers with no RDNS (they also block most ISP's from sending mail that isn't through their ISP's direct address).
Well, Drak over at HostNuke setup an RDNS for our main server so new signups should go through without a hitch.
Please note that this didn't really effect most freemail servers, but if you're one who hasn't been able to register because you haven't received the validation email, please try again now, it should go through without a hitch.
Thanks,
Gizmo