KITAS with wife as sponsor

This is a bit odd as a marriage within Indonesia is usually accepted without question.
A non Muslim marriage should be registered at the local area office and a letter of confirmation issued by them.
A Muslim wedding is rarely questioned as long as you have the marriage books. I was in the slightly odd position of a guy who was unsure of the rules asking me for the letter of confirmation but the chap at the local Catatan Sipil called immigration for me and sorted it out in no time.

The Catatan Sipil in the area you were married in is where you need to be to prove you are married if it was a non Muslim ceremony or the mosque if it was.
Asking for an immigration document from so many years ago is a tad unfair and probably not required.
If the Catatan Sipil can't help you, just go back and speak to a different immigration officer - fair chance he won't ask, especially if you are armed with marriage books.

There are too many "cowboy"marriages between foreigners and locals. Before moving here in 2015 at the Indonesian embassy in KL, I was asked, the first question, Where were you married? The second how long? In their opinion for wife sponsorship to live in Indonesia, wife should have lived with you in your country of origin for a minimum of 2 years. Foreign registered marriage is immediately recognized in Indonesia. At Catatan Sipil the same when Malaysia marriage cert. was produced, it was smooth sailing. My wife asked the officer does it make a difference where the marriage took place. The officer replied if local marriage cert. not acceptable if spouse is a foreigner. I suspect this is an unwritten law. Anyway just like immigration catatan sipil no longer can accept bribes.