Sargentks,
I assume you are now at iTunes Version 10.6.
May I suggest you take just one Song that is still stuck in "Waiting", perhaps one that you recently added direct from CD, and create a new ACC Version.
Then carefully follow the steps below.
I know, you said you have tried this, but, please try once again, carefully.
[Most of my "Waiting" status Songs were already AAC Audio File, 256 kbps (VBR), encoded with earlier versions of iTunes, but so were many of the Songs which iCloud was happy to accept. Re-creating the ACC Audio File just worked, for some strange reason].
In iTunes…
Select View, Options…, and check iCloud Status to display the status column,
best viewed as iTunes Album List sorted by Album…
a) Select Store, Update iTunes Match, [to ensure all songs are at the most up to date iCloud status],
b) select an iCloud Status "Waiting" Song, right click, Create AAC Version,
the Original and New version of the Song will be listed,
c) right click the Original version, select Delete, and check Also Delete from iCloud,
[initially, keep the Original version on file]
d) select Store, Update iTunes Match, and
wait until the iCloud Status indicates "Removed"
e) select the New version of the Song [the old will have been removed from you local iTunes list]
right click and select Add to iCloud.
f) be patient, eventually, the sat us will change to Matched, or Uploaded, as is appropriate...
If it works for you, do the above with multiple Songs selected, say one an Album at a time.
Like you, I struggled to sort this out on and off for a month or so, until I came across andbaum's entry above.
It worked for me, but I found the description a little cryptic, so I carefully documented and tested the steps, in the hope it may help other iTunes Users...
For some strange reason, recreating the ACC Version with the latest version of iTunes seemed to unlock the "Waiting" status.
Unfortunatley, I have no other magic to offer, so I do hope it works for you this time...
Robert.