Best solution to fixing database design with GUID as primary key
You certainly need NOT to cluster on the GUID.  If you have something which would allow you to uniquely identify records other than that GUID, I'd suggest you look at building an unique index on that other field &amp; making that index clustered.  If not, you are free to cluster on other fields, even using nonunique indexes.  The approach there would be to cluster however best facilitates splitting your data up and querying - so, if you've got a "region" field, or something, that might be a candidate for your clustering scheme.

The problem with changing to a BIGINT would be additions to the data from other databases &amp; integrating their database into the central store.  If this is not a consideration - and will never be a consideration - then, yes, the BIGINT would solve the index rebalancing issue nicely.

Behind the scenes, if you don't specify a clustered index, SQL Server does much the same thing: it creates a row ID field &amp; maps all other indexes into that.  So, by doing it yourself, you're solving it just as SQL would solve it.