First of all, I'd like to commend Nokia for their efforts at improving the Ovi Store.
It looks like the search works, finally! My applications have been indexed and I they appear in the search results when I use the corresponding keywords or the application name.
Something that seems to have changed is that your actual company name is now being displayed instead of the Public company name. Also, the Public company services description isn't being displayed on the publisher page. Is there any particular reason for this?