I just stumbled across this little gem

declare @x table ( i1 int, i2 int )
insert into @x values ( 1, 2 )
insert into @x values ( 2, 1 )

select *
   from @x
   order by
       case when 1 = 1
          then i1
          else i2
       end

select *
   from @x
   order by
       case when 1 != 1
          then i1
          else i2
       end

Works in 2000 and 2005. The example is a bogus when clause, more practically it'll be a parameter to your stored proc to pick the column to use for the output order. Go purge all that dynamic SQL you have just to get alternate output order.