What does Mail do when you try to quit it? For some reason, Mail takes significantly longer than most of my other apps to quit. It might become unresponsive for a period of time after I hit [command]+[q] before it actually quits. What is taking Mail so long to quit?
Turn on the Activity window to see what's going on. You probably have it set to purge deleted emails or some other shutdown maintenance. Press command-option-0 (command-0 if you're not on Lion 10.7) to see it or select from the Window menu.

I keep the Activity window up all the time just to see what's going on. But then, I have to monitor about 30 different email accounts for various work-related reasons.