I was having the same problem. The only way Waze seems to be able to find an address is if you hit the navigate button, then the "Favorites" button and then enter the address from there and mark it as a favorite. I tried to search for 2 addresses using the search box on the "Navigate" page and it didn't find either one. Once I went to Favorites, clicked "Add New Favorite" and searched for the addresses, it found them instantly. I have an iPhone 5 (iOS 6), so I'd think this would work for you as well.