Have a look at the quotas anyways, it will tell you if a user has an excessive amount of files stored on the server..
Quotas won't stop qmail-queue from creating a queue file - the qmailq user doesn't have a quota set. The message means what it says. The disk is full, or there are errors creating and writing files. The former is most likely.
> I seem to be losing email.
No, the mail should still be held elsewhere, and will be redelivered when you create room for it to be stored.
The "df" command will tell you about free disk space.
How to fix? Delete files. Not that the files will need to be not-in-use. If you delete files which are being used, e.g. some log files, then you won't create any free disk space.