Is there a way to undo transactions with a "too low" fee?
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.