Again, I appreciate the response. Sadly, I've looked at all of these support articles and they've been no help whatsoever. Perhaps a fuller description of what I'm dealing with will help save us some back and forth.
First of all, Match was working properly for me the first week or so after I signed up for it. From the start, I have had the following settings established on my iPhone:
Settings > iCloud > Account: properly logged in to the correct, main account
Settings > iCloud > Storage & Backup > iCloud Backup: On
Settings > Music > iTunes Match: On
Settings > Music > Show All Music: On
Settings > Store: Logged into the same correct, main account as above
Settings > Store > Automatic Downloads > Music: On
On my laptop - the computer I use to primarily manage my iTunes music collection - when I "Update iTunes Match", all but three songs are listed as "Matched", "Uploaded", or "Purchased", and I'm correctly told that "12,277 songs are now available in iCloud". I can live without those three songs so, so far so good.
But over the past week, music has been disappearing from my iPhone 4. When I go under Music > Playlists, none of my Playlists are showing. When I go under Music > Songs, it only lists 240 of the 12,277 tracks that are supposedly available in iCloud. Only 126 of around 1300 artists are listed. I have meticulously collected/scanned album artwork for literally every song in my collection, but a ton of it is now missing on even the few tracks that do show up on my iPhone, and on and on and on.
I've been trying switching settings on and off, logging out and back in, waiting minutes, hours, or even days between attempts, running a restore to previous backup for the whole phone, etc. But after days of frustration and time wasted - nothing. And the real kicker is that the whole music collection IS showing up just fine on my wife's iPhone 4 using the same basic settings - it just won't work on mine any more, and it's mostly my music to begin with!
Lastly, I know that in theory you can't delete a Matched song from your iPhone, but once I swipe-delete a track or album from the phone itself, it simply disappears from my phone forever. It does not remove it from the Cloud, but it is irretrievably lost on my phone.
So to summarize, I've basically eliminated that it may be user error, and have even discovered in these forums that others are experiencing identical issues to mine - typically once their device's memory has been filled up by tracks downloaded from the Cloud and they had to free up a bit of space as was the case for me. Yet no one seems to have found a fix.