BatchPatch is generally used with PsExec, not PAExec. In rare cases if a user is having issues with PsExec he might instead try using PAExec. I’m not sure in your case why you are using PAExec over PsExec, but I assume it’s because you had problems with PsExec functioning properly. That said, I’m not completely surprised to hear that there are PAExec services hanging around on some systems… the reason I’m not surprised is because there is likely something in your environment that was creating an issue for PsExec, and it’s conceivable that the same issue that was causing an issue for PsExec is also preventing PAExec from successfully and completely removing itself from targets where it is being used. BatchPatch does not remove PsExec or PAExec. They remove themselves immediately after they complete execution, but there can be cases where they fail to remove themselves completely/successfully.
You can manually delete a service with the following syntax at the cmd prompt on the server where the service remains:
sc delete ServiceName