Si, yo también me he dado cuenta que conforme vas instalando aplicaciones cada vez tarda mas en abrir la ventana de Widgets, supongo que será porque por cada APK instalado tendrá que buscar si tiene o no Widgets. No entiendo como Samsung (o a lo mejor es por Android) no "cachea" esa información después de instalar un APK.
Respondiendo a tu pregunta, los Widgets van dentro del APK así que no se pueden desintalar, posiblemente borrando los ficheros del APK antes de instalar la aplicación que hacen referencia a los Widgets no se instalen, pero también es posible que la aplicación se quede corrupta y de FCs.