Have you checked the transactions to see if there is a common web wallet you can locate? If non-web, there aren't many options to test..
I am fairly certain no desktop client deducts miner fees from the amount sent. MtGox charges 10x the min fee for withdraws but it is taken from account balance not the amount sent. I am fairly certain bitstamp and coinbase do the same. So it probably is some web wallet or smaller exchange. Not sure why people use exchange accounts as a spending wallet but they do. I agree with the OP it is an utterly stupid decision. I mean it break even "common sense". If I use my bank account to do a transfer, bill pay, or even bank wire there may be a fee but the fee is never deducted from the amount being sent. It would cause all kinds unnecessary chaos, support calls, and upset customers in the traditional finance world as well.
If any user (or any service, exchange, web-wallet, etc) can confirm an instance where a tx fee, or withdraw fee was deducted from the amount sent please post an example as someone needs to beat that developer over the head with a book on software design.
