I don't agree with the initial construct. I've seen plenty of indexes with compound keys work perfectly well for performance without the need to add another column and another index to the table in order to get performance to work. This would be especially true for two columns. You're talking about an index with a key that is 8 bytes wide. You're going to add a bigint column to the table, which is also 8 bytes wide, which saves what exactly? Adding a GUID, which is 16 bytes wide really doesn't save any space or make for a smaller index since it's twice the size.

Now, if both those columns are not very selective, so that the statistics for them is weak or horribly skewed, yeah, maybe adding another column is a possible solution, but I think we're talking about edge cases.

Also, be careful with GUIDs. They can lead to severe index fragmentation (which is not a big deal, at all, but is a possible issue) if you're using the GUID as a clustered index.