I also had luck with them responding within a month's time. I've made several requests (all in English), some with the record number and some without, and they still searched for me. I think if you supply the record number and parish name, you'll probably have a better chance at success, but none-the-less, they'll still search without it.
For anyone wondering where you might find the record number and parish name, you can try searching the following database first, to gather basic information, and then write away to Tunis for the actual record. This database is in French: http://www.geneanum.com/
The above link will let you can search for records in Malta, Tunisia, and Sicily.