Il redirect 301 dovrebbe in effetti far si che il vecchio url venga sostituito col nuovo. Ti consiglio innanzi tutto di controllare i vecchi url indicizzati e verificare la data della cache di Google, per verificare se sta continuando ad aggiornare i contenuti di quelle pagine o meno. Poi, per scrupolo, farei una verifica del 301, visitando uno dei vecchi url ad esempio con Firefox + Live HTTP Headers, per sincerarmi che effettivamente venga restituito correttamente il 301 e si venga poi rimandati sull'altra pagina che rende poi 200.