Не получается удалить Overlay

Вы объявляете переменную router внутри функции, поэтому эта переменная видна только внутри нее.

Сделайте так:

var router;

function list_route(value) {

    map.removeOverlay(router);
    var where_to = 'Москва';
    router = new YMaps.Router([value, where_to]);

    YMaps.Events.observe(router, router.Events.Success, function() {
    router.getWayPoint(0).setIconContent('Точка отправления');
    router.getWayPoint(1).setIconContent('Точка прибытия');
    map.addOverlay(router);
    });
}

А вообще, если не хотите стрететь все объекты с карты, то можно вызвать метод removeAllOverlays():

map.removeAllOverlay();