Navit can use openstreetmaps binary file for vector based navigation, but its unstable and not really that clean yet. I couldn't get it to find any addresses I searched for either. I am sure it will get there eventually.

EDIT:

What I would like is to see maemo mapper able to use Openstreetmaps vector files with the ability to search for an address via the openstreemap data or google.