Some of the recommendations here are incorrect.
- NEWSEQUENTIALID() is not allowed on SQL Azure.
- In SQL Azure, a clustered index is absolutely required. You can create a table
without one, but you will not be able to add data to it until after
you add the clustered index.
In Azure, the clustered index is used for their back-end replication. Reference: http://blogs.msdn.com/b/sqlazure/archive/2010/05/12/10011257.aspx
I think that your best bet is to use a column with an Identity element as the clustered index, along with a non-clustered index on your guid column. I ran into this exact same problem and after quite a bit of research, it's the solution I eventually came up with. It's a bit of a pain to put together, especially if you already have data in production on Azure, but it seems to be the one that addresses all of the issues.
I feel like it would be simplest to use a NEWSEQUENTIALID, but that isn't an option on Azure.