Haven't we had this discussion before? Well, it's probably a variant, so I'll explain again.
While klink may be right that those LS* files store the paths to your services-providing applications, when you log out or restart and then log back in again, those LS* files will be REBUILT, so when you still have the offending application in your applications folder or your offending service in your services folder, it will remain in the Services menu.
With that said, I must point out that applications sometimes provide services as do service files themselves. OmniWeb gives you an "Open URL in OmniWeb" service. So by this, it's probably fair to say that you have Quake in either your /Applications folder or your ~/Applications folder (the Applications folder in the root directory or the Applications folder in your home directory). Simply remove it from there (you could probably move it to a Games folder), and the service will be gone the next time you log in.
Since you said that you don't have Quake 3 installed, you might check anyway. Services can be present if the corresponding app/service is in /Applications, ~/Applications, /Library/Services, /System/Library/Services, or ~/Library/Services. Check all of these directories for anything that has to do with Quake.
Also, do a Sherlock or Locator search for Quake to see if you have anything related installed.
What does the service do, anyway?