Why do I get "No space left on device" when running mail

First of all I've checked these two solutions on serverfault but I'm still having issues.

Here's my problem:

root@myserver:/# mail
/tmp: No space left on device

• Firstly I checked the filesystem usage by running df -k but all filesystem usage was under 25%
• Then I ran df -i to check inode usage; maximum was 4% usage
• I have emptied /tmp and /var/tmp and still get above error

Pertinent information:

• I'm running Debian 6, postfix
• Recently had to remove a number of rogue scripts which were planted in user www directories. They looked like this: https://stackoverflow.com/questions/3328235/how-does-this-giant-regex-work these were being used to send high volumes of spam, and I've checked the mail logs and mail queue to ensure spam is no longer being sent. As a result, mail logs had grown very quickly. I have archived the large mail logs to another machine / deleted them, and done the same with all other large files in /var/log

Here's the output of df -h

Filesystem            Size  Used Avail Use% Mounted on
/dev/xvda              20G  4.0G   15G  22% /
tmpfs                 249M     0  249M   0% /lib/init/rw
udev                   10M  112K  9.9M   2% /dev
tmpfs                 249M     0  249M   0% /dev/shm
overflow              1.0M     0  1.0M   0% /tmp