Nope, not using any app like that. I have all the same apps that I used on cm7 - except not many are installed yet as I only moved to cm6.
Maybe a clean flash again - this time starting with 6.3.9? Wiping cache and dalvik doesn't help.
UPDATE: Found the culprit! And yes, it is an app. The app was "Blocker" or "Phone Call Blocker". It was not set to do anything for messages, only to block calls from private numbers. Disabled the service and tested notifications, and all was well.
Think the FC remains though - quickly went back to 6.3.6 for testing purposes, so not 100% sure yet.