I've long been a fan of logos on maps as an advertising opportunity that can also add value to the user. Over and above making it known that a store they may want is nearby, store signage helps with directions and navigation.
After all, which is more obvious to someone driving - a street sign or a McDonalds? So put golden arches on every GPS / UBD.