To test this out I disabled iTunes match and re-enabled it, and sure enough, I now get the exact same behavior. Apparently this is a new "feature." I'm going to go enter a complaint since there is no way to exclude these songs like there is for songs manually added to iCloud.
----------
Hey! I figured it out. This is what you have to do. Go to your iTunes library on your mac. Download the purchase. Delete the purchase from your iTunes library and make sure to check "Delete from iCould." It will then be gone from your phone.