Issue 1:
I think your intended ranking page is not indexed.
https://www.google.com/?gws_rd=ssl#q=site:http:%2F%2Fwww.localsearch.com.au
It's probably because, as Donna indicated, you have so many pages. This happens when you have what are essentially search pages that are indexed. Stuff happens like having a page for plumbing and plumbers in the same city, for example.
In the short term, you can make sure that non-indexed pages are linked to across the site. Long-term you're going to want to think of a way to organize your site to make sure Google and users can find the most important pages. For example, add breadcrumbs back to the city page, and have the city page linking to your most important types of pages (even if they're still searches) for the city. Right now your city pages are just more search pages, which is a big wasted opportunity to layout which pages you most want people to find. Also make sure you figure out what's going on between these two "types" of the exact same page. There should only be one for the same results where possible:
http://www.localsearch.com.au/Gosford,NSW
http://www.localsearch.com.au/Search?where=Gosford,NSW
Issue 2:
Look at the "linked from" and figure out where these bad pages are linked to on the site. Google wouldn't make up a URL if someone wasn't linking to them, and my guess is your site is causing them. With a highly-dynamic site like yours it's usually either a crawl trap or a combination of dynamic URLs through a particular path that the server wasn't expecting.
Alternatively, and maybe more likely, Google has been trying to parse Javascript lately, and doing a rather poor job of it. I've seen Google try to find links in Javascript that were never intended to be links. You can either ignore these errors and wait for Google to get better, or you can dig into the JS with a dev and see what's causing Google to interpret something as a link. There's usually another way to put the code together where Google understands.
