Recently there has been a lot of development regarding the address search. It now works on most Garmin GPS (only some automobile units are reported to not yet accept the address index). Just remember only Mapsource and Basecamp can write out the address index for the GPS, so the batch files to create a "gmapsupp.img" will not include address search. Neither can Qlandkarte GT.
In principal the address search works fine, on the limits that OSM address information is not well normed, and often entered wrongly. Basically every month this should get better (both in how mkgmap interpretes the data, and in the data itself).
I will post some more about this when mkgmap address search evolves.