Spazio archiviazione disponibile insufficiente

Ciao a tutti. Ho uno smartphone HTC wildfire S da 7 mesi circa.
Fino a poco fa scaricavo dallo store senza alcun problema. Adesso ogni qualvolta provi a scaricare un gioco o una qualsiasi app, ricevo questo avviso. Ho cancellato e disinstallato tutte le app inutili che avevo, tutti i giochi, la cache, e così via.
Non ho molto spazio sulla memoria interna e non ho ancora intenzione di "sverginare" il dispositivo, perchè perderei la garanzia.
Ho 12 Mb interni *circa disponibili più 4 Gb esterni. Anche apps di soli 100 Kb risultano impossibili da scaricare.
Come devo fare?