Captures cannot be undone either, but yes, that might be a problem. Go solves it with the ko/superko rule that states it is illegal to move in such a way to reproduce a previous configuration of the board, and I think the same rule would be relevant here.

Edit: another simple solution (with interesting strategic implications) could be to forbid moving the same piece twice in a row.

The best way to solve this is to say that you can't move a piece right back to where it just came from, like the ko rule in Go. As for superko, I think the threefold rule works just fine.