Got down and dirty on the source code and found the problem. The code that handes the search request for rooms was working fine (although I think it will be rather slow with too many rooms) but the result set was not being added to the response!
Thats why I never saw any matches. I just added one line of code, recompiled and now it works. I'll try and contact the authors so they can fix it, or I'll try to commit it to the svn myself.
In case it is usefull to anyone, the line I added is
On the line 340 of the file at src/java/org/jivesoftware/openfire/muc/spi/IQMUCSearchHandler.java.
I'll let you know when/if this makes it to the svn