Have you checked the connect.log on the client to see if discover patch is actually executing on the client machine? Can you send the patch_connect.log? Cross reference the connect log with the rcs log to see if any errors occurred. Also check the RMS logs for patch processing, or errors.
What version of patch 1.x, 2.0, or 2.01? Patch 2.01 has different table structure in the patch DB. You will see tables with the de2pa prefix. Can you send the rms.cfg file?
What bulletins have you acquired? All MS*, or only some MS*? Check the patch database to see if the bulletins have made it onto the patch database.
One other thing to check; there may be a ZSTOP method on the Discover Patch service, requiring you to do a Patch connect to resolve (ie: add dname=Patch to your radskman commandline). Depending on the PATCHMGR import, or database installation you did, the Discover Patch may have a stop method preventing the service from resolving. If you're not already setting dname=Patch for your radskman commandline, try it, and/or check for the ZSTOP command.