You overstayed your visa limit. Don't brush that off as a trivial offense. Immigration certainly doesn't.
It's good that you have kept your nose clean since then, but immigration is not "punishing" you. They are dealing with the matter. You have a black mark on your record. Now you want to marry a Japanese citizen in order to stay here. To them, it's a reason to deliberate whether you got married just for the convenience or not.
November to now is a fairly long time for most people to get a spouse visa. When is the last time you inquired with immigration about the status of your application? Sometimes that is all it takes to nudge them into taking action. Be polite and merely inquisitive, not demanding. I suggest you have your wife call.
BTW,
Turning oneself into immigration for overstaying can lead to only a year of deportation, and deportation is not an automatic punishment, either. Maximum is 5 years at the moment, but they are considering raising that to 10.
Permanent residence is usually given after 10 years of residence here. People married to Japanese can do it in about 5. Case by case. Getting citizenship requires 5. You could apply for PR if you like. It's free until you get word that you've been accepted, but I seriously doubt you would get it. Too short a stay, and that black mark, plus as far as we can tell, there are no extenuating circumstances which make you an indispensable part of society (one of the reasons for some exceptions to the time limit).