On a password leak from an e-shop

When the news broke about a password leak from xzone.cz, I felt uneasy.

I know I shopped there at some point… but I have no record of it anywhere in my KeePass. The server emailed users with information about the leak, a password reset (a new one is created by clicking a link), and last but not least we were warned to change our passwords on any other services where we'd used the same password.

The problem arises, however, when you have absolutely no idea what password you were using on that service. You don't know what it was, and there's no way to find out after the fact…

What do you do?