Is your service implemented as:
- (void)doSearchService

NSPasteboard *)pboard userData

NSString *)data error

NSString **)error {
...
}
Did you specify your service provider?
[NSApp setServicesProvider:objectProvidingService];
(You could do this in applicationDidFinishLaunching:, for instance.)
You can run in the debugger and see if your service is getting called.
Ali