Ben tam olarak anlayamadım biraz daha açarsanız problemi belki bir fikir verebilirim.
Daha önceki linkleriniz nasıldı? Şu ankilere bakıyorum kategori veya etiket temelli değiller direk link ve html şeklinde.

Ayrıca söyleyeyim kaldırdığınız sayfalar 404 sebep olduysa, bu sayfaları webmastertools daki url kaldırma kısmından kaldırmanız gerekli. Yeni sayfaları indexlemesi ne kadar sürer sorusuna kesin bir cevap vermek güç ama 3 hafta çok uzun da bir süre değil bunun için.

Bir kolaylık olarak da permalink finder diye bir eklenti var. Şayet link yapısı değiştiyse ve eski linklerle yeni linkler arasında benzer 2-3 kelime varsa eski linkleri 404 sayfası yerine yeni linklere yönlendiriyor.

Kolay gelsin...