Linux: no space left on device error with 50% free space

After spending a day crushing my head on the desk I would appreciate some help.

I'm running a Squid-Proxy on Fedora 14. Even if I try to touch /tmp/foo I'll receive a "no space left on device" error. I've already ran fsck. If I delete a file of say, 1MB, I'm able to store 1MB of data again but no more than that. Of note is that I have plenty of free space:

df output:

Filesystem           1K-blocks      Used Available Use% Mounted on
/dev/sda3             16311208   7614872   7867768  50% /
tmpfs                  1028548         0   1028548   0% /dev/shm
/dev/sda1               198337     55345    132752  30% /boot
/dev/sdb1             25803036  19407324   5084996  80% /mnt/squid-cache

Anyone have an idea what I can try to "reclaim" the free space?

At a guess you've run out of inodes rather than disk blocks - that is to say you have the limit on the number of files the filesystem can hold rather than the limit on the total amount of data.

You can use df -i to check this.