After some more testing, this seems to be the problem.

If I print "250 QUEUED - 123"

or "250 QUEUED(250) - 1084263071 qp 4221"

then everything works, but if I send:

"250 QUEUED(250) - 8c3d931926ca4e8a9dfea84f06dbdc1a"

then the client won't receive the above 250 response line. The 32 hexacharacter part is a GUID which I produce randomly using 16 bytes retrieved everytime from /dev/urandom. Now why would a proxy or a firewall regard a random 32 hexadecimal character as suspicious and block/filter it?