Windows 7 User here. Finally after searching forever about this problem, and trying sign out/sign in suggestions from Apple support I figured out something that worked for me. My problem was when I close the iTunes application re-opened it, I could SEE all my songs in iTunes Match but they were all greyed out and would not play. I would have to sign out/in - let iTunes rematch my library and it would work. Close the iTunes Application....rinse and repeat.
I created a new Windows User (mostly out of desperation) just to see what would happen. I installed iTunes using this user and THAT FIXED IT. Closed iTunes...reopen...can see and play all my songs, works flawless. This was a relatively new Windows install, so I ended up reformatting my HDD and creating a new user, still working great. I don't think one should have to go to these lengths just to get iTunes Match working, but I'm not sure if somehow the user/permissions or something had become corrupt. Hopefully this post helps someone else out there, like I said, I searched forever and no amount of signing in/out, deauthorizing/authorizing...or clearing caches or anything like that helped my situation.