Is there a way to undo transactions with a "too low" fee? Suppose we reach a state where only transactions that pay a fee are accepted by miners. Further supposed that someone created a transaction using an old/odd client that allowed them not to send any fees.

In this case, what would happen to the transaction? Could it be undone? Would the coins be lost forever?
The transaction would have no effect. A transaction that wasn't accepted by the network has no effect on the ability to spend coins. The person whose coins were affected could simply delete that transaction from his own database. There's no need to undo the transaction since it was never committed to the block chain anyway.