Does setting DEADLOCK_PRIORITY to LOW cause a stored procedure to run slower?
Going to guess here... transaction log file sizes

In the test system was small and grew when you tested the first time with LOW
When you re-run without LOW, then log file was already sized correctly.

Easy to verify: check the "lastwaittype" in sys.sysprocesses (deprecated but useful) to see if you gave LOG related waits affecting the SPID doing the DELETE.

Otherwise double check that the 2 executions are identical


same data
any triggers enabled
ditto foreign keys, indexes
foreign key cascades
...


Also see Why does an UPDATE take much longer than a SELECT?