That password I linked to is the very one they used to get into your Origin account, so how is it irrelevant?

The most likely scenario is this: you posted your password on a site that is filled to the brim with scammers and fraudsters, namely bitcointalk. One lucky guy saw that and threw it into his automated "Try this username/password-combo with every known interesting system" script, got a positive from Origin then threw it into his list of "dudes I have the Origin login data for". This fits with the timeframe also. You posted your password, two weeks later it's on the Russian site.