They still had to get the license.
Singstar only needs an audio track from a CD with separated vocals. Much easier to develop and churn that stuff out. European Singstar store has much more content then the American store though. I also think they charge the same as an RB song now which is absurd considering that you get up to 5 different instrument tracks in an RB track, 9 if you count pro modes and harmonies and with different difficulties.
Bloody hard to get good scores in Singstar vocals though even on Easy, it's brutal that way and I do expert RB Vocals.
Sony also has a record label or labels, I'm sure that helps to grease the wheels at times. Not sure what the percentage of songs on the games or store are actually from Sony labels
The thing is "Supermassive Black Hole" isn't 1 of those vocals only songs in SingStar. In fact it's part of the game "SingStar Guitar" as shown by the above list which has both SingStar vocals and 5 button guitar parts.
Not great quality but was the only vid I could find: