Mike,
My approach uses a combination of 595 (2 pieces) and direct outputs, as shown in the schematic here:
I could have used a third 595 to drive the rows and save some 5 outputs.
Since I dropped some "requirements", there are still 3 analog/digital pins available (for alarm/buzzer/x10, for example).
As for the input pins, I only need to use two: one is for IR receiver, one for a redundant push button. I am trying to funnel every user input through the remote control, including setting the time and the alarm.
Regarding the cost: the parts, PCB included, would run between US$60 (digikey) and $75 (sparkfun).