You may not be able to get complete matches, but here's what I have been doing in the cases where one or two tracks don't match.
- Select the item(s) to attempt to re-match.
- Right-click on them, and select "Create AAC Version"
- When this is complete, hit alt-backspace, and choose to remove both the original and the iCloud version. Also choose to delete the items from disk.
- Go to the "Store" -> "Update iTunes Match" menu item.
Note that this will keep the play counts, etc on your tracks. It may not succeed on every track, and sometimes repeating the process picks up another track.
Occasionally, I'll get a "Removed" icon there after doing this: just right-click and choose "Add to iCloud" on these.
Some research led to this article from AllThingsD about how an Apple rep had confirmed that the service does indeed stream the music, but it also saves to the device, thus taking up storage space. It starts playing before it finishes downloading, but it does actually download and save.
MacRumors and a video from InsanelyGreatMac are somewhat unclear about this, but MacWorld agrees that on an iOS device, it's downloading (scroll down to "Playing iTunes Match songs on your Mac and on iOS").
UPDATE as per comment:
As of iOS 5, the device will delete cached data from apps when it's low on space. This caused some controversy at first because apps had no way to prevent cached data from being removed automatically. In the linked article, Marco Arment provides an example:
A common scenario: an Instapaper customer is stocking up an iPad for a
long flight. She syncs a bunch of movies and podcasts, downloads some
magazines, and buys a few new games, leaving very little free space.
Right before boarding, she remembers to download the newest issue of
The Economist. (I think highly of my customers.) This causes free
space to fall below the threshold that triggers the cleaner, which —
in the background, unbeknownst to her — deletes everything that was
saved in Instapaper. Later in the flight, with no internet
connectivity, she goes to launch Instapaper and finds it completely
empty.
This was fixed in iOS 5.0.1 (Apple Developer documentation) so that developers can differentiate between cached data that is and isn't important.
So, the short version: Once free space gets below a certain level, the device will regain whatever space it can by removing cached data from installed apps. If it can't do that, or if you're completely out of space, it'll probably just tell you that you don't have enough space to do what you're trying to do.
Best Answer
You don't need to download a song on your iOS devise via iTunes Match to get its artwork updated on that device. All you need to do is go into Settings -> Music -> turn off iTunes Match, and then turn it back on. All artwork will update over a few minutes. (I turned device off and back on again before turning Match back on just to be safe, but not sure it's necessary.)
You can go into your Music and see the little spinning wheel constantly working a half second at a time (for each album cover being updated from A to Z). with iTunes recent update to artwork, this is how I got the new artwork over to my iOS device.