Well, let me say this first #$##$ $#*&#$^ $#&^#@@!&%^#@ %#*&^$# godaddy $#*&#$*#&#$*&#@ #$*&#$ godaddy #$&^#&^#$ #$## godaddy... Ok.. a little better now. I did the censoring myself as I already know that kind of language won't fly on just about any forum.
Godaddy has been zero help on this issue and that's an understatement.
Anyway, I recently had a client say that all their emails were giving this quota warning and it's been going on for awhile now. I did some testing and sure enough, I would get the alert back pretty quick. For the heck of it, I decided to setup a global mailbox quota of 50mb for the domain and repeated the previous test exactly the same and never received a warning. I went to his webmail and all the emails were received. I figure 50mb should be plenty enough storage for any normal person and even for those people who insist on forwarding 2mb joke files every 10 minutes (any webmaster could rant for an hour on that subject alone).
So, for now the problem seems resolved, but I'll be sure to post an update in a few weeks to let everyone know if it's definately working.