After several months of not having any search on my site, I decided to add it again. Frankly, I missed it myself, as I use this site as an archive for stuff that I need.
So I did some googling and came up :

Voodoo Programming » Blog » LiveSearch

I may want to go through the code of the plugin as it has a lot of inline javascript, but for now, it is working...