Darren,
I would still suspect permissions. Check the permissions of the .qmail file.
Have you tried to create a new user and see if the email for that new user can be delivered.
If it can then use that to compare all file permissions.
Have you installed or modified anything recently.
Jon