Si están en Skydrive y de allí nunca lo borraste, siempre que sincronice con Skydrive, te vuelven.
Ahora, si lo borraste de Skydrive, teniendo el celular conectado con Zune a la PC, en las opciones de sincronización, poné que la misma sea para las imágenes, del celular a la PC.
Una vez hecho esto, dentro de Zune, vas imágenes del teléfono y borras los álbunes que quieres borrar y no vuelven más.
Espero que te haya servido mi mala explicación....