Conclusion
Here is my conclusion regarding the overhead of using ordinary GUIDs for the primary keys:
Indexes need more frequent rebuilding with GUIDs. That also applies when updating statistics.
You must be prepared to see inconsistent INSERT throughput at different times.
The scalability for INSERTs isn't good because the INSERT overhead increases rapidly.
With my COMB algorithm, the three problems mentioned disappear. The problem with the large overhead in size is there both with my COMBs and with ordinary GUIDs. (After all, COMBs have the format of GUIDs!)
But GUIDs have a lot of advantages, too. (These are sometimes so big that you really don't have a choice!) In my opinion, using GUIDs as primary keys is often a very good idea (especially if you go for the COMBs instead). Is the overhead or the advantages more important when it comes to your applications?
Special thanks to Vladimir Suponitsky and Tibor Karaszi!