Hola,
A mi me ha pasado lo que comentas con mi Nexus One: cuando apagaba y encendia el movil desaparecian las fotografias que habia hecho y volvian a aparecer las que habia borrado (que aparentemente antes de reiniciar parecian que se habian guardado y borrado respectivamente).
Al borrar alguna imagen tambien se me ha llegado a bloquear el movil y se quedaba la ultima imagen como congelada de fondo.
Tambien los iconos de algunas aplicaciones desaparecieron y aparecia como que no los tenia instalados (estaban en la tarjeta micro sd).
Y el problema era ese, que estaba rota la tarjeta micro sd de la marca Sandisk, de 4gb, y eso que solo llevaba usandose un par de meses...
Probe restaurando el sistema que venia de fabrica en el propio movil (borra todo) y formateando la tarjeta en el ordenador (en Windows y Linux). Parecia que se le daba formato bien, pero cuando volvia a poner la micro sd en el movil todo seguia igual. En Linux daba un error como que el indice de ficheros estaba mal.
Bueno, he cambiado la micro sd y ya esta todo solucionado ;)
Un saludo.