Claro que se puede, desde el PC puedes formatearlo como te dé la real gana. Yo he comentado cómo lo formatea la PSP por su cuenta.
A mí modo de ver, la diferencia es inepreciable de FAT16 a FAT32, tanto desde la PSP como desde cualquier otro dispositivo. Tiene sus ventajas y sus inconvenientes.
Por cierto, HAL9000, a mí eso que dices me pasó y mi MS es Sandisk auténtica. Desde entonces uso FAT32, pero no he notado ninguna diferencia de rendimiento (también es que uso Ultra II), así que no he probado en formatear de nuevo en FAT16.