Here's what I had to do :
After going through this harrowing phase, I thought I will post an update in case some one is in such a situation. The Northern Territory's Personal Violence Restraining Order act has a clause (section 21) which basically says if the applicant believes a third party knows the defendant's name then the applicant can request the court to order the third party(power, water, electoral roll, etc) to provide the name if the applicant has already made reasonable efforts in finding out the persons name and hasn't been able to. The third parties will only oblige to a court order.
I am almost certain every state/territories' act (in Australia) will have such a clause. It was a challenge to get the court registry to accept the application as the front counter staff/supervisor/supervisor's supervisor were all unaware of this provision (to make an application for a PVRO but get the judge to first order the third party). I had to carry with me the act with the highlighted portion for them to read, analyse and consult with other court staff to even take my application in.
At least in the NT there are community legal help services available for no fee and I highly recommend them.