Si has reinstalado el TNV y nada, ya se convierte en un problema raro que afecta a la memoria de la Vita.
Si formateas desde el modo PSP, que no he tenido que hacerlo y no se si lo permite TNV, pero de permitirlo solo borraría lo relacionado con PSP, haz copia de seguridad de lo importante para ti y prueba.
el problema parece residir en la Memory Stick (virtual en este caso)
A las malas solo te queda el backup y restaurar la base de datos de la consola e instalar el TNV de nuevo. De estas cosas hemos aprendido todos, se optimista