Even though Ashley's solution solved it for a while the problem happened again therefore I tried her solution again. But it didn't stop. It happened again.
Today, it came to my mind out of nowhere that some playlist not syncing while some others were successfully syncing might be due to the ineligible songs in those not syncing playlists. And that seems to be the case.
I removed all of the ineligible songs from those playlists and they instantly showed up on my other devices.
In order to show the ineligible songs in your iTunes, you have to click the header of the songs view in your library and select iCloud status. Selecting this will add an additional column about each of your songs' iTunes Match status.
This seems like a bug in iTunes Match since it can sync playlists with ineligible songs at first but not afterwards.