Hey William,
There is clustering on the primary key.
We are running SQLAzure, not SQL inside an Azure VM.
We're at the P4 pricing tier right now.
What we've done to mitigate this...
1. SQLAzure has no SQL Jobs nor does it re-index your tables automatically. Instead we created an Azure Automation job that uses a PowerShell workflow to re-index all indexes in a given database. Currently we are doing this every hour as the fragmentation on the OutboxRecord soars after only 30 minutes (greater than 90%).
2. The other issue is that since we have 7 instances of this service running in Azure Worker roles, we cannot set the to a short time frame, because then each instance tries to issue delete commands against the database every 5 minutes. Instead we set them to one day, knowing that the delete issued by the NServiceBus host will fail.
3. To purge old records in the OutboxRecord table, we've created an Azure Automation job that uses a PowerShell workflow to accomplish this. It looks at the OutboxRecord table and deletes anything with a DispatchedAt <= DATEADD(HOUR, -1, GETUTCDATE()).
I've attached both workflows for other people that might need the same thing. #3 allows the deletes to be consolidated and only run once (as opposed to per service). This seems to have mitigated the table from filling up and the slow performance.
The next thing we're trying is to recreate that table with Partitions, and to then roll off old partitions. This will hopefully allow us to keep our data a bit longer and not need to be so agressive in our cleanup. It will also reduce the amount of fragmentation happening which should also improve INSERT performance.