I tried your scenario with 3.4.c and it worked flawlessly for me.
I created a space under Company Home, gave the guest user consumer rights, and when he then used the link to that folder, he was not only able to see its contents but also to search for and find it.
Do you mean, that the search field in the upper right disappears, when you have a guest with consumer rights?
If not, maybe you gave permissions on a file level in your folder? Is your problem limited to search? Did you use wildcards* ?(but with or without, your search results should not vary with the level of the guest's access right)
Can you reproduce your problem with an empty Alfresco installation?