Les messages SMS sont stockés dans la mémoire interne de votre téléphone, généralement à cet endroit.
/data/data/com.android.providers.telephony/databases/mmssms.db
De plus, si vous avez installé des applications, elles sont généralement installées par défaut dans la mémoire interne, sauf si vous avez spécifié le contraire ou si vous utilisez Froyo ou une version supérieure ou une autre variante de Apps2SD, etc.
Vous pouvez utiliser une application comme Sauvegarde des SMS et archiver les SMS sur votre compte Gmail ou sur une autre application SMS telle que GoSMS qui permet de sauvegarder/restaurer les SMS de la carte SD.
Par ailleurs, essayez de libérer de l'espace en déplaçant/désinstallant les applications dont vous n'avez pas besoin et en vidant le cache de votre navigateur et les données des autres applications. Une application comme Cachemate pourrait aider si vous êtes enraciné.