Does the second call of the SP wait for the first call to end? It should skip the rows locked by the first call and delete the next ones.

Have the proper indexes on your table and make sure your queries always use that index. Are you missing ROWLOCK (which will use more resources in this case)?

Let me know if this helps.