Gentlemen, I believe we're over-complicating the original question with talk of compressibility and EAS (although I am finding it quite interesting).
Wilfred - if we consider only TAS and IAS, then TAS Vs will increase with altitude, and IAS will ramain the same, for the reasons you outlined. Remember that, taken from the lift formula, '1/2rhoV* = IAS'
And I do believe EAS Vs will increase slightly with altitude. I might have to verify with the 17 or 18 text books I've got up in the shelves though.
Great thread and answers folks...