Eliminar de CTE con unión

Puedes usar exists() en lugar de la unión interna a MyTable en el CTE.

with cte as 
(
  select top(1) q.id,
                q.col1
  from queue q with (readpast)
  where exists(
              select *
              from  MyTable a 
              where  q.id = a.myTableID AND 
                     a.procID = @myParam
              )
  order by q.Data asc
)
delete from cte
output deleted.ID, deleted.col1;