I am not a black hat SEO expert by any means, so take my thoughts with a grain of salt. It sounds like you may have been the victim of a negative SEO attack. In short: one of your competitors may have created these millions of spammy links in order to decrease your rankings (and, presumably, raise their own closer to the top). If this is still a site you care about, consider disavowing the spammy links: https://support.google.com/webmasters/answer/2648487?hl=en
Thank you for the encouraging words! I had no idea that those would work (testing non-roman characters totally slipped my mind). So, I'm really glad they do!