I personally find that the users prefer the CloudMade API in terms of the quality of results that come back from geolocation searches.

The maps work fine, and the site could do with an update... but where CloudMade struggles is the design of the maps. At certain zoom levels (quite zoomed in) and within particularly dense areas (centre of Paris and London) they're just ugly. Which would be fine were it not for the fact that where there is high-density there is also a lot of users.

Both CloudMade and MapBox allow you to run custom styles... but unless you are a designer and/or cartographer who knows what you're doing, you're likely to make a hash of it.

Getting a good design for maps is very very hard, making something ugly is shockingly easy. Neither CloudMade or MapBox can prevent this, but at least MapBox's default is really quite beautiful.