Yahoo! Australia & NZ Local Search

Just found this, looks and acts very similar to the new Sensis service, however it is easier to use and quicker to find things.

Give it a go and see what you think.