Why am I getting "write queue file: No space left on device" from postfix when there's 5GB of free space on disk?

You might want to run a df-i to see if you have used up all your inodes.

You can have available storage space, and not have the ability to add files.

cache:~# df -h
Filesystem            Size  Used Avail Use% Mounted on
/dev/sda1             132G   68G   58G  55% /
cache:~# df -i
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sda1            17514496 13543293 3971203   78% /

You also might want to check to see if you have any quotas set (repquota -va).

5% (iirc) of space is reserved for root, might be your filesystem is "full" for normal users. You can get more info with e.g.

tune2fs -l /dev/sda1

Which device is full? Perhaps there's plenty of space on one partition, but another (e.g. /tmp) is full? Do a df -h and see if any of the partitions are close to full, and then figure out if postfix uses that partition.