I am working on fixing a database that uses GUIDs (i.e. uniqueidentifier) as primary keys.  Our customer does a high number of inserts and generates their keys from their application or from NEWID().  In addition, their primary keys are clustered.  There are many articles on the Internet that talk about the problem of using non-sequential GUIDs as primary keys.  Kimberly Tripp over at SQLSkills has a good article here.  The short description of the problem is that generating a non-sequential key can create fragmentation.  Unless you use a function that generates sequential GUIDs, like NEWSEQUENTIALID, you are bound to see fragmentation.  Additionally, a GUID is an unnecessarily wide key and can bloat your non-clustered indexes and add significant overhead in terms of wasted space and query performance.

I love GUIDs as keys, but not primary keys.  In order to fix this problem, I created a database generated identifier (i.e. IDENTITY) as the primary key with an integer (i.e. int) data type.  I then create a unique index on the original GUID which gives me the benefit of having the best of both worlds.  First, a small, sequential identifier that is highly optimized for querying, joins, and storage.  And second, a globally unique identifier which I can share outside my application.

NOTE:  We see this problem all the time.  That is what happens when you have developers manage your database.