Yes, they do. Generally they don't pay royalties on individual songs, they are more likely to contract for a specific collection of songs or artists, or even an entire label.
Here's what Synthesia says about this on their site.
Songsterr explains this in their terms of service.
Songsterr is backed by U.S.-based Guitar Tabs LLC and it is 100% legal. We have great relationships with music publishers, all of the content provided through our Service is licensed, and we pay a percentage of our revenue as royalties to support music creators.
If you find your own work being distributed you could sue, but these services generally provide a way to report such incidents, and you would probably want to start there rather than going directly to court.