Theoretically, this should not happen, and it's not your responsibility to fix it (nor is there any way for you to do so as things stand). As long as you have iTunes Match turned on, you should see your files exactly as they were uploaded. Any subsequent changes you make (on any device) should also be broadcast to all of your devices. If this is not happening, it's a bug within iTunes Match. Unfortunately, such a bug does exist, and Apple knows about it.
I suggest you contact Apple and let them know the service you paid for is not working as expected, and let them fix it.
I have found a solution...
The first issue is you have to know what songs are missing art and you need to have that list of songs on the machine that is NOT missing art.
On the computer that shows the MOST album art missing make a smart playlist that will display songs where album art is false. Then make a standard playlist on the same computer and drag all the songs from the smart playlist to that new standard playlist.
Now you have created a standard static playlist that shows all the songs that it is having issues with album art that you can view on the computer that has art.
On the computer that had the most album art correct (hopefully for you that one is a MAC) if you install this script http://dougscripts.com/itunes/scripts/ss.php?sp=reembedartwork from Doug's iTunes scripts.
And then run the script on all the songs in the newly created playlist.
NOTE: The script will fail if the song has NO album art on the computer your using so make sure you have manually fixed the few remaining songs without art. For me this computer has 100% of the art so it was not an issue.
This script takes each mp3 out of iTunes embeds the image within it and then puts it back with all the same tags and keeps it in all the playlists. This process caused iTunes Match to re-sync the song and the album art on all songs started showing again on all computers.
Having the images embedded in the mp3 is important I guess for iTunes Match.
So the smart playlist on the computer that had 100% of the art was empty.
So I went to the computer that had the most missing art and the same smart playlist on that PC said about 400 songs had no art. I then copied that list to a standard playlist. So I made a static (not smart) playlist that now lists the 400 songs that this computer says has NO art.
I then go to the computer that has 100% of the art and I load the static playlist (not the smart playlist on that system because that system says 0 songs in that playlist) and see the 400 songs the other computer says has no art. Turns out all 400 of them have ART on THIS computer.
So i then run the script I talked about above and that modified all 400 MP3s to embed the art within them. That proccess made a change to iCloud Match and now all computers that go to the cloud get updated with the correct album art.
Hope that is a little more clear... if not ask away and I will clear it up. (It is not an easy topic to wrap your head around at the best of times!)