Running a DELETE stored procedure but finding degradation in performance in WHILE loop as iterations increase
You say that performance degrades with the number of executions and that "restarting the deployment" fixes it.

I'm unclear what you mean by that particular phrase but presuming that it involves stopping the loop and then restarting it after some period then one possibility is ghost records.

I created a table as below (with one row per page for easier maths)

CREATE TABLE T
  (
     X INT PRIMARY KEY,
     Y CHAR(8000)
  )

INSERT INTO T
SELECT TOP 100000 ROW_NUMBER() OVER (ORDER BY (SELECT 0)),
                  'Y'
FROM   master..spt_values v1,
       master..spt_values v2


And assumed your DELETE process is clearing out older rows as identified by some ascending column.

SET STATISTICS IO ON;

DECLARE @i INT = 0;
WHILE @i &lt; 10
  BEGIN
      SET @i+=1

      RAISERROR('Processing %d',0,1, @i) WITH NOWAIT

      DELETE TOP (2000) FROM T
      WHERE  X &lt;= 50000

      /*50 MS Delay*/
      WAITFOR DELAY '00:00:00:050'

      SELECT ghost_record_count,
             version_ghost_record_count
      FROM   sys.dm_db_index_physical_stats(db_id(), OBJECT_ID('T'), NULL, NULL, 'DETAILED')
      WHERE  index_level = 0
  END 


Results

+---------------+--------------------+----------------------------+
| logical reads | ghost_record_count | version_ghost_record_count |
+---------------+--------------------+----------------------------+
|          2018 |               2000 |                          0 |
|          4025 |               4000 |                          0 |
|          6033 |               6000 |                          0 |
|          8026 |               7965 |                          0 |
|         10004 |               9944 |                          0 |
|         11989 |              11920 |                          0 |
|         13977 |              13902 |                          0 |
|         15963 |              15882 |                          0 |
|         17954 |              17864 |                          0 |
|         19943 |              19849 |                          0 |
+---------------+--------------------+----------------------------+


Records aren't deleted straight away. They are marked as ghosts to begin with then cleared up by a background task. In the test above very few of them were cleaned up in the 10 iterations meaning that the tenth DELETE did 10 times as many reads as the first one.

Possibly in your environment the DELETEs are occurring at a greater rate than the ghost cleanup task processes them leading to the continual degradation of performance.