There are two towns named redcliffe, one near Perth, the other near Brisbane. If you chose the wrong town from the list, it can't find the street. I'm in Europe, so I don't have Australian Maps installed. The search in Navit is sometimes difficult, but if the data is there in OSM, it should be there in Navit, too.
Try without house number.
https://www.openstreetmap.org/node/1547 ... /153.11284 has an Irene Street, so that should be found. There are very few buildings in the map in that area, and thus no house numbers. Henry Street Number 2 is there and thus should be found.