А как Вы мереете время при выполнении Job-a? Profiler-ом, постоянно обновляя свойства работы или как то еще? И как его запускаете - по расписанию или руками?
(Просто возникло глупое подозрение что если запускается по расписанию, а вермя окончания, например определяется по факту обнаружения вставляемых записей в таблице, то все дело просто в рассогласовании ваших часов и часов на сервере на несколько минут )
И еще - как много раз Вы проводили запуск? Не может ли быть что при запуске Joba на таблицу была наложена блокировка, а при запуске скрипта в QA - нет?