You can avoid a lot of these types of issues using a digest for the username and password plus a master key as a salt. It generates a unique and relatively complex sequence for each site and doesn't require any persistent state other than the salt.

The downside is a lack of control over complexity and the issue of passwords being strictly dependent on the salt. So, if one set of credentials is compromised, you would need update them all.

I've seen software that does this, but there are subtle details to consider to actually get it correct.