Proof of Communication I desire an algorithm in which Alice sends a block of data $X$ to Bob, with proof that the data was both sent and received.  Ideally this would take the form of a public-key signature of the block $X$ by both Alice and Bob, so that each is in possession of (X + sign(X,A) + sign(X,B)).

Further let us assume that Alice and Bob both may have motivation to lie about having sent/received the communication.  Bob may choose to lie depending on the contents of $X$ once he sees it, and Alice may lie to attempt to discredit Bob.  Therefore the signatures or other proof of communication must be revealed simultaneously to both Alice and Bob.  At no point may either be in possession of the proof while the other is not.  

I'd put a bounty on this if I had any reputation, but hopefully people will just consider it an interesting challenge.  Some notes that may help:  This is closely related to the Two-Generals problem (for which there is no two-party solution), however due to cryptography orders may not be forged, so I hold hope that there may be a two-party solution.  If not, a multi-party solution (using witnesses) is acceptable.  An example of an algorithm which simultaneously reveals information is Diffie-Hellman, but the shared secret there cannot be chosen by either party, so cannot itself contain any information.
This sounds like "fair exchange," the subject of many good research papers. In general you need a third party to give any security guarantees, but "optimistic fair exchange" involves the third party only when one of the parties tries to cheat (i.e., when both play honestly there is no involvement from the third party).

Incidentally, Diffie-Hellman is most certainly not fair: whoever sends first lets the other party compute the key before the original sender can.