As noted in a previous Knowledge Base article, there is a bug in Mac OS X 10.5.6 that causes it to report no search results when searching against AFP servers other than Mac OS X 10.5, including Acronis Files Connect (formerly ExtremeZ-IP), Mac OS X 10.4 (Tiger), Mac OS X 10.3 (Panther), and Microsoft's now discontinued Services for Macintosh (SFM) on Windows 2000 or Windows 2003.
Upgrading to Mac OS X 10.5.7 will solve the problem. Also, if you are using Acronis Files Connect 6.0 or later, you can enable Network Spotlight search support. Mac OS X 10.5 clients will then use Network Spotlight for search, which is not affected by this bug. More details on setting up Network Spotlight can be found in this best practices document.
Before Apple released 10.5.7, Group Logic tested and recommended a workaround involving Find Any File, a free standalone application that can perform a search correctly from any Mac OS X 10.4 or later client including Mac OS 10.5.x. This workaround is still valid if for some reason it's not possible to upgrade to 10.5.7 or use the Network Spotlight support in Acronis Files Connect 6.0. Find Any File is freeware available from http://apps.tempel.org/