I don't have iTunes Match and don't use iCloud so I can't speak for that. Normally if you see a ! by a song it means iTunes has a reference for it but the actual file was missing when iTunes last checked (usually at startup). If you click on it and it suddenly plays it means the file has reappeared. A common situation for this is where somebody has media on an external drive and their library files on the internal drive. They start up iTunes without the external drive fully mounted and iTunes doesn't see the files, but then they start the drive and when you click on the track and iTunes has another look it is suddenly there and plays. I know you didn't say this was your scenario but maybe there's something else going on similar to this. Do you manually manage media, or keep media on separate volumes?
How did you remove the files from your Macbook? Again, I don't have Match but I thought some other icon would appear for those songs.
iTunes Match: Understanding the iCloud Status icons - http://support.apple.com/kb/TS4124
By the way, I hope you have your files archived on a drive at home too. Match is a convenience feature but not a place to store your only copy of music.