Новые урлы, поисковики и 301 редирект

В общем, суть такая. Когда-то некие говноразработчики сделали сайт с URL вида /index.php?page=catalog&cat=56&id=89. Было решено сменить эти урлы на более приличные вида /catalog/56/89 или что-то типа того. Вроде бы есть такое, что, если сразу поменять урлы везде, то сайт провалится, да и все ссылки, которые есть начнут вести на несуществующие страницы. В принципе, ничего не мешает делать 301 редирект на страницы с новыми адресами. Вопрос в следующем: не вывалится ли сайт из поиска, если резко поменяются сразу все урлы на новые, а старые будут делать 301 редирект? Если вывалится, то стоит ли делать «постепенную замену», то есть, например, сделать так, чтобы раз в неделю, допустим, 10 позиций в каталоге меняли свой урл со старого на новый и так до тех пор, пока все не поменяются? Какие у кого есть мнения на этот счёт?