Malware caused "Search With Google" service to be named "Search With Trovi" I'm dealing with a Mac that has been affected by some kind of Trovi malware - I've managed to undo most of the changes but there is still one I can't figure out.

The malware renamed the "Search With Google" service to "Search With Trovi". My fixes have sorted out the functionality of the service, in that it now successfully launches a Google search in Safari, but the name is still wrong. See pictures below.

Any ideas how to fix this?

I've tried searching the names and contents of all files on the Mac (including invisible files, and including those in packages) for instances of the text string "Trovi" but have had no luck.
The service name "Search with ..." is dynamically created and depends on your favorite service engine selected in Safari > Preferences > Search > Search Engine. So choosing a different search engine (e.g DuckDuckGo) in Safari will also change the service name (i.e. "Search With DuckDuckGo").

To remove Trovi completely, download, install and run MalwareBytes Anti-Malware for Mac or an antivirus app like BitDefender. You may also have to remove Safari extensions related to Trovi. A list of known malicious extensions can be found here: Remove Trovi Search from Apple Mac OS X (Removal Guide)