Can anyone suggest how to find what Internet service could be available in my area?

The typical website designed to give you that answer is a fraud in Australia. It seems to be designed to answer "yes" even when they know it should be "no" because there is no penalty for deceiving customers that way.
I wanted to move to a particular area late 2016 and searched that website for the availability of the Internet before committing to a lease agreement. After entering the intended address in Telstra,s web site, I got the glamourous answer: "Great news .. is available at your address..", I then signed a 1 year lease, moved and ordered the Internet and phone package but the reality was the only wired telco in Australia cannot connect although they sent a modem that never showed anything other than a red LED. This was after I had asked my previous ISP (TPG) to move the existing Internet connection to this new address and this ISP never answered until both cases became my subject of complaints with the "Ombudsman", both wanting to charge or continue to charge for a service that was closed and the other for a service that knowingly never worked as the Telstra technician stared at the red LED claiming ignorance of the gadget (of course, he could not tell me what he knew for fear of losing his job).

Lately, I have tried to google Internet services for that particular area and found that many providers still advise to use the same search website and I am under the impression that if the telco (Telstra) is unable to make the connection at their local exchange, nobody else can either but I could be wrong as it all seems to be a complex web of services designed by our politicians creative but unqualified imagination rather than engineers.

There are other ways of getting the Internet but I know nothing on the subject.

Just to give you an idea, my attempt at relocating my existing Internet connection was made in October 2016 (TPG) and their first answer was given in February 2017. My "application" for a phone/internet with Telstra (the telco) was made in February 2017, supplied about 4 weeks later and notified within days that it was not working, but still unresolved today (11 Aug 2017) although Telstra is still expecting the monthly payment and I cannot wait any longer as it could take years.

Any hint or reference most welcome.

Thank you for your help.

Here, there are a few ways to access internet
* Wired, overgrown from telephone companies (grown from handling 300 baud modems). These days, in Ireland, there's a Government financed glass fibre network, and short local wired dsl type feeds to individual houses, Plastic Optical Fibre would probably be better and doable. I'm getting the best part of 40MB/S that way. The State phone company owns the infrastructure, but everybody resells the service.

* As an option outside cities, some companies do radio links of varying quality. There is a Optimal spot for aerials which overlooks my city, and they have a microwave link up there. That's line of sight transmission to an A4 sized transceiver aerial on the roof.

* As an option out in the wilds, there are satellite internet services using geo-stationary satellites. In Ireland, where it rains every day, some clouds are visible 100% of the time and no sky is visible 50% of the time, this is a last resort. You may have better results in Oz. A search for 'satellite internet service australia' was productive.

* Mobile internet via wifi hotspots are also an option. 4G is *@$£! fast.

I would ask internet users locally what they use and is it any good.

I'm in Albany WA
I use Omninet, not the cheapest but pretty good service
they are local to Albany and I think use Debian on their servers
so they are linux savvy and tech savvy
http://home.omninet.net.au/

I found the only answer was "mobile broadband". Initially, I thought that was reserved for telephone communication but it is also available to use with a PC through what they call a "pocketwifi" wich only needs to be connected to the electricity power point.
In my case, I have been told (true or not) that my good reception (a bit unexpected) could be due to the fact that there are not many subscribers in my area.