ASPState database locking and growth problems
I suspect you implemented Greg's replacement procedure as pre-emptive optimization. The one-row-at-a-time approach restricts locking to a single row, sure, but it's going to take a lot longer - especially if you force SQL Server to attack rows in a random order.

My suggestion would be to revert to the original procedure:

ALTER PROCEDURE dbo.DeleteExpiredSessions
AS
BEGIN
  SET NOCOUNT ON;

  DECLARE @now DATETIME;
  SET @now = GETUTCDATE();

  DELETE ASPState..ASPStateTempSessions 
    WHERE Expires &lt; @now;
END
GO


If you find that this becomes a performance issue because of the locks taken, you can split this out and even reduce impact on the logs using something like:

ALTER PROCEDURE dbo.DeleteExpiredSessions
AS
BEGIN
  SET NOCOUNT ON;

  DECLARE @now DATETIME, @c INT;
  SELECT @now = GETUTCDATE(), @c = 1;

  BEGIN TRANSACTION;

  WHILE @c &lt;&gt; 0
  BEGIN
    ;WITH x AS 
    (
      SELECT TOP (1000) SessionId
        FROM dbo.ASPStateTempSessions
        WHERE Expires &lt; @now
        ORDER BY SessionId
    ) 
    DELETE x;

    SET @c = @@ROWCOUNT;

    IF @@TRANCOUNT = 1
    BEGIN
      COMMIT TRANSACTION;
      BEGIN TRANSACTION;
    END
  END

  IF @@TRANCOUNT = 1
  BEGIN
    COMMIT TRANSACTION;
  END
END
GO


This is going to be much better, IMHO, than using a randomized cursor to delete one row at a time. You can tweak the value in TOP (1000) based on actual observation.

A couple of other ideas that might help:

(a) set the ASPState database's recovery model to simple (it defaults to full).

(b) change ASPState_Job_DeleteExpiredSessions to run every 5 or 10 minutes instead of every minute. If this job is taking > 1 minute to run then it is going to always be running. Hopefully it isn't completely linear, meaning that waiting 5 minutes instead of 1 won't queue up more than 5 minutes of work instead of 1. Implementing my suggestions above should help with this.