IPhone :: ICloud Stream Files In 4 Sync List?

I turned on iCloud when it first launched, then immediately turned it off because using iCloud didn't display my music correctly on my iPhone 4. Instead, most of the album art was missing (including for files that were actually stored on the phone) and it ignored my album sorting. Therefore, I opted not to use the service.

Ever since though, I have these "stream" files left over from when I used iCloud. What I mean is, if I look at the Music list on the iPhone when it is connected to my Mac (so when I hook up the iPhone and click on "Music" from the left nav), I see a bunch of songs greyed out. When I right click on those files, they say "Not Available" for the Kind attribute and "Stream" for the Size attribute. I am unable to play them and all other information on the other tabs, e.g. Song Name, are greyed out. Cleary they are files from iCloud that are still on my phone despite turning off the service.

This wouldn't bother me except for that fact that the songs that have this issue are missing from my phone even though they are checked in iTunes and selected in my Sync settings. So, I am not able to play them on my iPhone. For example, the entire Please Please Me album by The Beatles is missing because all of the songs on that album are these "ghost" stream files. The only way to resolve this is to delete them from my iTunes library and then add them back in. When I do this, the songs finally sync with my iPhone. However, I am looking for another solution because I don't want to have to delete and add 100s of songs and I don't want to lose the meta data, e.g. play count. I've tried unchecking/rechecking the affected songs in iTunes. I've tried unchecking the artist in my Music settings. Nothing has worked. I have a iMac from July 2011 running latest version of Lion. I am also running the latest versions of iTunes and iOS.

Info:
iPhone 4, iOS 5.1.1