I think you are confusing a few things. There are lots of different maps and services using OSM data, and some of them update more frequently than others.
eg the standard view at openstreetmap.org (also known as ‘Mapnik’) usually updates within a few minutes or hours.
Or the Open Mapquest maps usually seem to update pretty quickly, sometimes a few days.
OpenCycleMap can also take a few days to update.

Note that for these map tiles, they may not update all zoom levels at once. So things might seem to disappear as you zoom in and out. Its also possible you are looking at a cached version, doing a Shift+Refresh in your browser might help.

Any updates to routing services are separate from these map tiles.
eg on YourNavigation, it says at the bottom of the page “Routing data from planet file: 2011-12-09”. So it won’t use any changes since then, I’m not sure when it will next be updated.
Or there are other routing services using OSM data, eg Open Mapquest http://open.mapquest.com/ It usually seems to be fairly up to date, though note it is not necessarily as up to date as the Open Mapquest map tiles are.
Or more routers listed here: http://wiki.openstreetmap.org/wiki/Routing/online_routers