Unfortunately an extra 4.5119 was also sent to him that he is refusing to return. (I understand that this is partially Bitcoinstore's fault)
While it likely will be lost in the scam vs counter scam accusations but the error in the OP has a relatively simple fix. BTW I have done the same thing and it was a LOT larger than 4.5119 BTC. Luckily (and yes I had that sick feeling in my stomach until it was resolved) for me the person who was double paid was a regular repeat customer and stand up guy who promptly returned it.
So the relatively simple fix. bitcoind should have a delay send feature. An parameter which when set in configfile indicates the number of seconds a transaction should be held before sending.
delaysend=120
Before someone freaks out about "reversing payments" this would simply be client side. (assuming delaysend=120 is set)
1) user sends x BTC to address y (x or y may be wrong)
2) client provides transaction id
3) for the next 120 seconds the tx is NOT broadcast to the network.
4a) In the GUI a cancel button can be shown (which disapears after tx is broadcast).
4b) In bitcoind a new two new RPCs are added.
CancelDelaySend [txid]. txid is optional. Calling it with no txid will abort all queued delay sends
OverrideDelaySend [walletpassphrase]. Wallet passphrase is required even if wallet is unlocked (see hot wallet below).
5) delaysend expires and tx is broadcast normally
Honestly I would put some coins towards a bounty (a portion for a functional patch, and another portion when included in mainline).
This would also provide some (although not complete) protection for a hot wallet.1) hot-wallet password is NOT stored on server.
2) hot-wallet password manually entered by admin when bitcoind is started (with no expiration on locking hot-wallet)
3) DelaySend can't be modified once bitcoind is started. changing it requires bitcoind reset (and thus admin password).
4) DelaySend can be overridden but requires admin password.
If attacker attempts to send funds using the bitcoind it will be delayed for x seconds giving admins a chance to double spend the attacker from a backup wallet and get a head start in any race. The hotwallet password isn't available on the server in plaintext. The wallet.dat (actual file) is still encrypted. It can be decrypted from the key in memory but that is a slightly more sophisticated attack. In the event the server still has outside communication admins could call the 'lockwallet' RPC to flush the decryption key from memory. Alternatively cutting actual power to the server or power cycling (via remote PDU with separate login credentials) would result in a locked wallet and erasure of any DelaySend txs.
Note this isn't foolproof but it does raise the bar compared to the totally simplistic current attacks (login as admin, use servers own hotwallet bitcoind to send out funds or locate passphrase in code and grab a copy of wallet.dat). It gives admins a fighting chance if the intrusion is detected early.