How about we had two different types of stars, one that depends on the percentage of notes hit in the song (Standard one), and another one that is depended by the highest possible score to get in a song and how much of that you actually got.
Example:
So the yellow ones are the standard ones while the red ones are the score-based ones.
I think the best approach for this would be to, before the song starts, let the PC 'scan' all the notes in the song. It will then have to calculate the highest possible score of the song, as it scans, it will store the score in a variable.
This variable will increase by 50 for the first ten notes, twice as much for the next ten, three times as much for the notes after that and then four times as much for the remainder of the song (Because of the multiplier), of course it also has to add additional points depending on the length of each note.
This variable will be in the memory of the PC while the song plays until where it is needed to calculate the red stars, after which the variable is reset (or discarded)!
Just an idea I wanted to share, so... How about this?
iwant this one done 
