[b]

"Memoria Piena. Eliminare qualche dato".
[...]

Ho provato a cancellare i messaggi, ma il kb relativi rimangono gli stessi (diminuiscono quelli della stessa voce della memory card).
Non è che hai installato programmi voluminosi in ram?
Oppure hai una cache con molti file.

Prima di buttarlo, salva i dati principali (rubrica, sms .. insomma quello che vuoi salvare) e fai un reset totale del telefono. Sicuramente quei MB di memoria li riprendi.