I've had the same problem, albeit (thankfully) on a much smaller scale, with my Irish residency. I've been here over six years but I "lost" more than a year due to bureaucracy and the failure of my previous employers to file my work permit renewals on time. Not my fault, but nothing I can do about it.
> The day a party propose voting right for people who are on any non-
> temporary visa (ie equivalent to tourist or short term business) and
> how have been in Japan for a relatively long period of time (maybe
> something like more than 3 years), I'd consider them serious about
> the issue.
Here, you get voting rights in local elections after six months, and if you're an EU citizen you can also vote in European elections. These are EU requirements, I think.