I know a guy who overstayed for years but he is a businessman and quite a large employer over there and it was a long time back, he just used to pay the fees, the actual overstay fees were not that high if I remember correctly, I think it's a daily rate of some kind.
I take it you did not pay these fees the last time you exited the country? Or were you caught and deported?
I know a two lads that are good lawyers that have helped us a lot, it was a couple of year back and in relation to immigration issues for my partner, I will drop them an email and ask if can pass you their contact details.
Jim