It'll sound dumb, are they accessing your site through:
http://yoursite.tld

or
http://www.yoursite.tld

I ask because I think the search forum sends the search to the www version of your site and they may not be logged into the www version (as the "www" on your domain is meerely a subdomain the cookie would be set on whatever url they logged in on).

I am a Web Development Contractor, I do not work for UBBCentral. I have provided free User to User Support since the beginning of these support forums.
Do you need Forum Install or Upgrade Services?
Forums: A Gardeners Forum
UBB.threads: UBBWiki, UBB Styles, UBB.Sitemaps
Longtime Supporter & Resident Post-A-Holic
VNC Web Services: Code Modifications, Upgrades, Styling, Coding Services, Disaster Recovery, and more!