NeilXP,
I went through this same issue recently with my Surface Pro 2. It worked just fine until some firmware bricked my keyboard port (not the Type Cover itself, but the connector port/pins on the Surface).
I went through every silly troubleshooting step, reinstalled fresh and restored factory image, numerous times. I even bought a second Type Cover 2 only to find it didn't solve the problem.
You might be in luck... Since you have the Surface Pro 4, it should still be covered by some kind of support. I don't mean warranty, unless you have the warranty, then MS would be obligated to replace your device.
I mean End of Life dates. MS has strangely removed EOL dates online (?), but my SP2 EOL date was April, 2018 (funny, that was 1 month before my Touch Type Cover stopped working). Therefore, it's very doubtful MS would ever "fix" the firmware for the older SP2. Although, morally, they should fix it, but they aren't going to waste resources and time on an older device that is past its EOL date.
Your SP4 released in 2015 surely has not reached End of Life, and MS should provide some kind of support until 2020 or so (it's usually 5 years). At least a chance for future firmware updates to fix it. After 2020, you may as well sell it or buy yourself a Bluetooth folio type cover case.
This problem drove me nuts for nearly a month until I realized the EOL thing and gave up, and bought a new 2017 Surface Pro on Ebay, which I'm currently typing on and LOVE. And I made sure to get the extra warranty in case this happens again.
In your case, you should contact MS for support and even if they charge you a labor/repair fee, at least they are obligated to fix it or give you something newer if they can't. Being in Australia, you might have to ship it somewhere.
I'm surprised after your MS phone support for 1 hour, they did not request for you to send it in for service? Did they just give up?
Good luck man, I feel your pain and am very familiar with this issue! I'm a certified Microsoft tech but I do not work for MS.