At last I managed to purge the unused locales from the rootfs.

Since there is no localepurge package for maemo 5, I just grabbed "localepurge" and from the armel package from debian and copy the files manually to /usr/sbin. There is a version 0.5.8 for Diablo. I just used the latest 0.6.2 from debian squeeze. I didn't want to move locales to /opt as I would have to do it for every app installation. Instead of cooking up my own script, using localepurge seems to me a better and safer solution.
Anyway, after some tries I found that both UTF-8 and ISO-8895-1 are necessary. I chose the easy way:
1. Run "dpkg-reconfigure locales" & select "en_US.UTF-8 UTF-8" AND "en_US ISO-8895-1".
2. Run "locale-gen" once to generate the needed locales.
3. Run "dpkg-reconfigure localepurge" and select only those to keep. Choosing high verbosity will give you more options of how locales are purged, such as whether to purge man pages and show how much space is saved, etc..
4. Run "localepurge" to remove all the unnecessary locales. In my case around 20MB of rootfs space is reclaimed.
Reboot to test the result. No more gibberish.

The hard way:
Edit /etc/locale.gen and /etc/locale.nopurge. Note the difference in how locales are specified. For example, for US English locales,

in /etc/locale.gen, it should be something like:
en_US ISO-88951
en_US.UTF-8 UTF-8

while in /etc/locale.nopurge, it should be
en_US
en_US.UTF-8

You can also configure localepurge easily by simply (un)commenting the options in the file.