> How would they prove the integrity of the data leaks?
Most jurisdictions already have security breach notification laws. If you're already required to report data loss to customers and/or the government, then at that point I don't think it's unreasonable to require companies to provide a copy of any leaked credentials since they should all be deactivated anyway.
> How would you prove that the password is reused, and how'd determine the size of the fine?
If companies were required to turn over credentials that had been breached, then this would be determined from the entire set of breached credentials.
> Does it matter if the password is strong, but reused and one of those services stores it in plain text and is hacked?
Sure, that's exactly why you're not supposed to ever reuse passwords even if they're strong.
> Would it be legal to use a weak password for a service if the hashing algorithm is strong, or just as long as the service isn't hacked and the data leaked?
I think there should be some minimum entropy level that's required regardless of the hashing algorithm. E.g. given that passwords can be automatically generated and stored, there is zero reason ever to use a password that's less than 30 characters of completely random characters.
> what you're suggesting requires at least two other crimes to be committed
The fact that these crimes are interconnected is why such a law is needed in the first place. And all these attacks are automated, so if you're reusing your last.fm password on Facebook and it takes ten minutes to brute force your last.fm password, then your Facebook account is going to potentially be pwned in ten minutes and 1 second.
If there were some benefit to having weak passwords then that would be one thing, but the way I see it it's just people creating a national security risk out of pure laziness.