Using the API you would be displaying a map which is created with somebody else's map data. That somebody else believes that your application should be therefore paying a license for using that data

For the turn-by-turn navigation service is the user that pays a license, through Nokia Maps.
Making a deal with the data providers is easy, Nokia obviously has such a deal thus Nokia products can use the map data in whichever way and form covered by that license.
What is complicated is making that license available to developers which would transform Nokia in license reseller ...
My advice is to get in touch with e.g. Navteq and see what offer they have, both for APIs and data licensing. In the Smartphone Show I've seen a demo with more wow effect than the Map & Navigation API can provide at this time. See
http://developer.navteq.com/site/glo...s/ms/index.jsp