Thanks everyone. The only reason I suggested changing to Varchar was my hope the value would evaluate the same and not force a re-order of the index, but it sounds like it wont.

I am adding a BigInt, Identity column to each table in question, and as time goes on we will back populate the ID with the GUID. It sounds like there is no middle ground here, and we will have to bite the bullet for some tables by dropping the indexes and recreating them.

To load these tables we use MSMQ, and can turn off the queue's while some of this is going on. Since this is on 2008, any advice on doing these changes "Offline"...? We will be dropping the clustered index, and moving it to the BigInt column to avoid the page locks.