Pour fournir un service minimal, tu peux même utiliser le serveur officiel openstreetmap.org. Mais si tes utilisations sont excessives et/ou abusives, ils peuvent te couper le service (blocage par Referer HTTP, User-Agent HTTP et/ou adresse IP, selon la source de l'abus (respectivement: site web, application, utilisateur)). Si tu veux l'intégrer à une application publiquement téléchargeable, tu as intérêt à demander avant (cf. consignes d'utilisation), mais si tu respectes les consignes (User-Agent valide, utilisation de cache etc.), je pense que ce sera généralement accordé (en tout cas, il y a plusieurs applications qui ont obtenu la permission: Marble, plusieurs applications mobiles dédiées etc.).

Oui, le User-Agent peut être faussé, mais il en est de même pour une clé API. Il n'existe pas de moyen incontournable pour identifier une application. Le concept d'identifier une application a d'ailleurs ses limites dans le contexte de logiciels libres où les forks existent.

Pour les utilisations intensives, il faudrait comparer les prix des différents fournisseurs.