Slow & Complicated Update

I have the following stored procedure that I use for an update. The table now has just over two million rows and the stored procedure takes days to run. I am looking for any help that would produce the same results faster. This runs on SQL Server 6.5, on an NT machine with 4 pentium pro 200 processors and 512 MB of RAM so I am relatively sure that the performance issue is in the below statement.

UPDATE PAY_CHECK_DETAILS
SET JobID = j.JobID
,HROrganizationID = j.HROrganizationID
,JobDetailID = j.JobDetailID
,GLAccountNumber = j.GLAccountNumber
FROM JOBS j, PAY_CHECK_DETAILS p
WHERE j.EmployeeID = p.EmployeeID
AND j.HRActionEffectiveDate =
(SELECT max(HRActionEffectiveDate)
FROM JOBS jj
WHERE p.EmployeeID = jj.EmployeeID
AND jj.HRActionEffectiveDate <= p.PayDate)

AND j.HRActionSequence =
(SELECT max(HRActionSequence)
FROM JOBS jjj
WHERE p.EmployeeID = jjj.EmployeeID
AND jjj.HRActionEffectiveDate =
(SELECT max(HRActionEffectiveDate)
FROM JOBS jjjj
WHERE p.EmployeeID = jjjj.EmployeeID
AND jjjj.HRActionEffectiveDate <= p.PayDate))
AND NOT (ISNULL(p.JobID,1) = ISNULL(j.JobID,1)
AND ISNULL(p.HROrganizationID,'A') = ISNULL(j.HROrganizationID,'A')
AND ISNULL(p.JobDetailID,1) = ISNULL(j.JobDetailID,1)
AND ISNULL(p.GLAccountNumber,'A') = ISNULL(j.GLAccountNumber,'A'))

Thanks for any help or suggestions you have.
Keith