This seems to be fixed. I can search using wildcards on Edgy and get results. It's still marked as unconfirmed on the Gnome Bugzilla. Jedie, can you confirm this? -- wildcards should work with the search feature https://launchpad.net/bugs/41704