An option which no one has really mentioned is to use those extra digits for special purposes (ie Change tempo, another instrument). If the primary instrument is a piano, I'd imagine that simply assigning a digit to the snare, bass and cymbal would add a lot of flair to your final music.
In fact, adding new instruments will open you up to a bunch of new ways to do this. You could let each digit represent an operation. Each operation could represent an instrument, tempo, or effect change, etc... Also, each operation would then read in as many more digits as it needed in order to satisfy it's parameter count. This will allow for your beats to have things like sustain, accent, etc... for your notes.
This will actually make the problem of having more data space than note space even more of a problem except for the fact that it was never really a problem to begin with. Just pad the extra space with the next higher and lower octaves. This will result in a slight imbalance of notes but we don't really want a balance anyway...
Which does lead us to another problem. I think your best bet is to use patterns found in popular music to ensure that your note dispersion is pleasant. I found this site which has the data we'd want for determining that:
Your application will be more likely to sound better when it produces notes with a similar dispersion pattern to this. You may find that some instruments may work vastly differently though so (as with all of this) experimentation will be important.
Once you have this system working, I'd suggest trying to think of another song which it sounds similar to what you have and doing a more exact note dispersion graph which actually matches a song in the same key. Read the page at the link above to see what I mean.
If you wanted to step it up another notch, you'll have the ability to add as many functions as you want. You just need to decide how large an op code is (1,2,3 chars) depending on how many different functions you have and handle them all (even if large blocks of them do the same thing). If you really want this to be a complex symphony, I would suggest that you separate the processing step from the playback step to eliminate any timing issues you'll have due to the variable data rate inherent to such a design. Fortunately, there are standards. One popular standard is called MusicXML. If you make your program to simply generate those files. Then you can later play those files back using a MusicXML player.
Update: If you'd like to see my experiments with this you may get them here.