>Don't use stored procedure for inserting one record.
>
>If you want insert more then 1000 records, then use XML.
>Yes, you can pass XML to stored procedure as parameter (VARCHAR(MAX)).
>
Good point, it wasn't clear to me (either way) if he was calling this procedure a large number of times, one row at a time. If that's the case, then that's definitely an issue as well.
In addition to the XML solution, since he's using SQL 2008R2, he could pass a table type as a parameter instead of XML. That's *probably* likely to be even faster.
But the possibility of an ordered index using a randomly-generated uniqueidentifier could also be the culprint (and should be addressed with regular maintenance if it's not so already).