This is running much slower for you than it should. Your query is instantaneous on my laptop as well. I even created 10K rows of sample data and tested it. This query takes a couple seconds on my laptop:

declare @table table (someXML xml);
insert @table
select top (10000) replace(cast(@p2 as varchar(1000)),'1003381', user_type_id)
from sys.all_columns;

SELECT t.col.value('@ID','BIGINT') AS ID,
  t.col.value('@PrimID','INT') AS PrimID,
  t.col.value('@AuthID','INT') AS AuthID,
  t.col.value('@ProgID','INT') AS ProgID,
  t.col.value('@ServiceCodeID','INT') AS ServiceCodeID,
  t.col.value('@WorkerID','INT') AS WorkerID,
  t.col.value('@Date','DATETIME') AS [Date],
  t.col.value('@StartTime','DATETIME') AS StartTime,
  t.col.value('@EndTime','DATETIME') AS EndTime,
  t.col.value('@RequestID','INT') AS RequestID,
  t.col.value('@GPermID','INT') AS GPermID,
  t.col.value('@PayRateOverride','VARCHAR(30)') AS PayRateOverride,
  t.col.value('@AutoScheduled','BIT') AS AutoScheduled
FROM @table x
cross apply x.someXML.nodes('/ROOT/R') AS t(col);

T-SQL XML queries against XML are going to be slower than ones against tables no matter what but not 21 seconds a row. As Luis mentioned sp_xml_preparedocument, I too, have had some success with that.