This is unacceptable. I have mine configured as well with paytxfee=0.0 and yet transactions I put through bitcoind on command line or with json rpc are applying a fee.
I just put in a transaction 73c294e732dac0b0cfe2da6633aec7cd66616d4b9f9e27b629bda31f8d8e1f5e for 0.0192 which generated 0.0005 in fees. We need to be able to block the user from making a transaction that will put their account balance negative. To me this is a pretty serious bug, that I've told it to send no fees and yet its sending fees instead of throwing errors.
I felt the same way when i first figured that out. The bitcoin client would warn you a impending transaction fee but when sending from command line (bitcoind) it does no such thing. As such from a commerce point of view this can get tricky, which 0.0005 is small amount but from what i understand if the transfer is large enough its possible to incur higher transactions fees which would kinda of suck.
I would propose that you could put in place a fixed transfer fee for all transactions (i.e 0.001) if you are running a free service or absorb the transfer fees if you're running a "for-a-profit" operation as part of doing business
Cheers