differential patching predates Microsoft's foundation as a company. Differential patching has been optimized for binary data (executables, images) since well before the 360. A few years ago an even better method was conceptually developed, but I don't think too many people have made use of it yet.
I have no idea what the Microsoft patent thing could possibly be referring to.
Has Steam been implementing this to some extent? They've been changing the storage format for a lot of games (The Witcher 2 was a problem one) to allow for smaller updates.