Embedded Artwork is the key to seeing your album covers...
I don't know if this has been discussed in the 7 pages here, I didn't read through them all, but what I have discovered about the iTunes Matching and Cover Art that is important to be able to get all the art to show up on your devices from the cloud is that each song/file needs to be tagged with the art. So that when you look at the albums from the file system, and drill into where you see the songs, you see each MP3 or M4A in the finder, that each song files icon has the album art on it.
I tested this out, had an album that had been tagged with art in iTunes, but looked at the files and they weren't. Added that album to match and no art work was sent up. Then I tagged all the files that made up the album with art and updated Match and then it showed up. There are several ways to get all the files tagged with art, I found a script someone wrote online, and have been using it to tag them quicker, especially quick if you already have the art tagged in iTunes but its not showing up on the files themselves.
Here is the script I installed and use:
http://dougscripts.com/itunes/scripts/ss.php?sp=embedart
Embedding the Art into each file is key, because if you think about what Match is, its doing it song by song, so the state of each file is important, and if the file doesn't have the art embedded, then you won't see it up in the cloud or on your devices using the cloud music.
You may have to play with turning off Match and then turning it back on with each of your devices to see the new changes.
Essentially what I've done is created a separate iTunes Library, where Im slowy adding essentail music from my huge 38,000+ library (master).
Each time I add one, I check that it has all the album artwork embedded in each file, thus slowly uploading and seeing each album with art on all my devices.
I can do an artist or two at a time and its getting to where I'll eventually have a nice 25,000 song library up in Match, ready for my devices to use as intended.
Hopefully Apple does know about these issues with large libraries and gets something working so its not such a PITA.