Problem fixed... somehow...
Ok, so I had exactly same problem on brand new installation. I'm using Postfix. I enabled DomainKeys, SPF, DNS Blackhole and DrWeb right after installation. Everything was ok until one user attached 3Mb file. Got 451 Error: queue file write error.
I did multiple tests and it seemed to occur only with messages > 1 Mb. I disabled SPF, DomainKeys, DrWeb many times. No change. Finally I disabled all 4 AND restarted server. Problem is GONE.
Now I'm going to enable spam prevention systems one by one and see what happens.