This might be of use to you as well -- ClearCoin escrow: http://clearcoin.appspot.com/
The first 100 BTC of each transaction is free, with the escrow fee at 1% for anything over that.
So to protect yourself when sending, you can put the amount you are sending in escrow and then immediately release it. The result is a publicly visible record that N Bitcoin were sent to XXXX...XXXX address on a date that could have been one of three different values (depending on whether the escrow expiration was 1 months, 6 months or 12 months out.).
Here's an example of a completed transaction that occurred on Dec 7, 2010: https://clearcoin.appspot.com/status/r_T89JAvkdiuTHbWCHCKyFTF
That, along with the instruction from the recipient showing what Bitcoin address you were supposed to send payment to, ... and you end up with a pretty convincing argument that the funds were truly sent.