Changes don't show on GMAPSUPP.IMG

Most likely all you have to do is to wait. Depending on where your GMAPSUPP.IMG is from it might only be regenerated once a week.

Re the second question (and you really shouldn't ask multiple questions at once): That depends on which Garmin unit you use.

Re the first question, you're probably nothing wrong - as petschge said, you'll need to wait until whoever creates that file for you creates a new version. An alternative might be to use something like "mkgmap" to create a map yourself (see my answer here if you want to do that).

Re the second question:

1. The map that you download must be routable. We don't know where you got your gmapsupp.img from, so can't really comment on that.
2. The software used to create the map must be capable of creating address-searchable maps. The most commonly used (mkgmap) isn't quite, yet, although development is ongoing. However, with mkgmap-created maps you should be able to search for e.g. cities and POIs without issue.
3. Some newer Garmin devices may have or have had problems with some routeable maps. Although you don't say what device you're using, I'm guessing (because the menu says "Where To") that it might be a newer one such as a Nuvi. Personnally, I've found relatively few problems with routing to e.g. POIs with a Nuvi 265w.