Queries slow in stored procedure

I have a stored procedure with some serious business logic in it (about 2000 lines).
When executing the SP, I'm faced with a big performance issue.
Part of the SP contains queries which are running in a matter of seconds in query analyzer, while in the SP itself they take forever.

To illustrate the magnitude of the problem, below you can find an extract of the SP.
Every step finishes about instantaneously in query analyzer, while via the SP it takes 45 seconds EACH !

Any idea how to boost the performance ?

ps : I'm not using any calling parameters for the moment in the SP, so I believe it's not really related to parameter sniffing. And from an indexing perspective, the necessary ones have been created. Volume wise, temp8 contains 52000 records, temp9 about 10.000 records and temp13 only 3600.

Extract from SP :

--STEP 1
update T
set validfrom = T1.min_vf
FROM dbo.temp9 T
INNER JOIN
(select routdestntimediffelmid, costtraffictypeid, suplproductid, min_vf, min(tempid) tempid from dbo.temp9 group by routdestntimediffelmid, costtraffictypeid, suplproductid, min_vf) as T1
ON t1.routdestntimediffelmid = t.routdestntimediffelmid and t1.costtraffictypeid = t.costtraffictypeid
AND t1.suplproductid = t.suplproductid AND t.tempid = t1.tempid

--STEP 2
update T
SET validfrom = T1.validto+1
from dbo.temp9 T
INNER JOIN dbo.temp9 T1 ON T.tempid = T1.tempid+1
WHERE T.validfrom is null

--STEP 3
Update T1
SET rthours = p.total FROM
(select q.routdestntimediffelmid, q.costtraffictypeid, q.suplproductid, q.validfrom, q.validto
, SUM(case when q.rhourto > q.rhourfrom then q.rhourto - q.rhourfrom else 24-q.rhourfrom +q.rhourto end) total
from
(select distinct t8.routdestntimediffelmid, t8.costtraffictypeid, t8.suplproductid, t9.validfrom, t9.validto, daycode, rhourfrom, rhourto from dbo.temp8 t8
INNER JOIN dbo.temp9 t9 ON t8.routdestntimediffelmid=t9.routdestntimediffelmid
AND t8.costtraffictypeid=t9.costtraffictypeid AND t8.suplproductid=t9.suplproductid) as Q
group by q.routdestntimediffelmid, q.costtraffictypeid, q.suplproductid, q.validfrom, q.validto) as P
INNER JOIN dbo.temp8 T1 ON P.routdestntimediffelmid = T1.routdestntimediffelmid
AND p.costtraffictypeid = T1.costtraffictypeid
AND p.suplproductid = T1.suplproductid
AND t1.rdtde_vf <= p.validto AND t1.rdtde_vt >= p.validfrom
AND t1.c_vf <= p.validto AND t1.c_vt >= p.validfrom
AND t1.rdtc_vf <= p.validto AND t1.rdtc_vt >= p.validfrom
AND t1.tdi_vf <= p.validto AND t1.tdi_vt >= p.validfrom
AND t1.sdc_vf <= p.validto AND t1.sdc_vt >= p.validfrom
AND t1.tdis_vf <= p.validto AND t1.tdis_vt >= p.validfrom

--STEP 4
UPDATE dbo.temp8
SET overlap = dbo.fncalculateoverlap(rhourfrom, rhourto, shourfrom, shourto)
DELETE from dbo.temp8 WHERE overlap = cast(0 as numeric(15,2))

--STEP 5
/*------------------------------------------------
- CREATE NEW REDUCED TEMPTABLE
------------------------------------------------------*/
INSERT INTO dbo.temp13(routdestntimediffelmid, costtraffictypeid, coverage, suplproductid, supldestnid
, supltraffictypeID, COST, CurrencyID, currencytypeid, VD, comment, codetype, validfrom, validto, totaloverlap, rthours)
select t8.routdestntimediffelmid, t8.costtraffictypeid, t8.coverage
, t8.suplproductID, T8.supldestnID, t8.supltraffictypeID, T8.cost, t8.currencyID, t8.currencytypeID
, T8.VD, T8.comment, t8.codetype, t9.validfrom, t9.validto, t8.rthours, SUM(overlap) totaloverlap
FROM dbo.temp9 T9
INNER JOIN dbo.temp8 T8 ON t8.routdestntimediffelmid=t9.routdestntimediffelmid
AND t8.costtraffictypeid=t9.costtraffictypeid AND t8.suplproductid=t9.suplproductid
AND t8.rdtde_vf <= t9.validto AND t8.rdtde_vt >= t9.validfrom
AND t8.c_vf <= t9.validto AND t8.c_vt >= t9.validfrom
AND t8.rdtc_vf <= t9.validto AND t8.rdtc_vt >= t9.validfrom
AND t8.tdi_vf <= t9.validto AND t8.tdi_vt >= t9.validfrom
AND t8.sdc_vf <= t9.validto AND t8.sdc_vt >= t9.validfrom
AND t8.tdis_vf <= t9.validto AND t8.tdis_vt >= t9.validfrom
GROUP BY t8.routdestntimediffelmid, t8.costtraffictypeid, t8.coverage
, t8.suplproductID, T8.supldestnID, t8.supltraffictypeID, T8.cost, t8.currencyID, t8.currencytypeID
, T8.VD, T8.comment, t8.codetype, t9.validfrom, t9.validto, t8.rthours

--STEP 6
Update T1
set BCOST = Q.cost
From
(select routdestntimediffelmid, costtraffictypeid, suplproductid, validfrom, max(cost) cost from dbo.temp13
where coverage >= @BCoverage
group by routdestntimediffelmid, costtraffictypeid, suplproductid, validfrom) as Q
INNER JOIN dbo.temp13 T1 ON Q.routdestntimediffelmid = T1.routdestntimediffelmid and Q.costtraffictypeid = T1.costtraffictypeid
and Q.suplproductid = T1.suplproductid AND Q.validfrom = T1.validfrom

...

1. run perfmon with the physical disks counters, reads/sec & writes/sec
first run this set from QA, then in a stored proc (Called from QA or your app?)
is there a difference in disk activity?

get the execution plans from QA and from the stored proc
is there a difference?

run from QA and from a stored proc
this time with
SET STATISTICS IO ON
SET STATISTICS TIME ON

provide the messages output of each (not the data)

After some further investigation, I do obtain exactly the same timing results between query analyzer and the execution of the SP. This by setting the parameter FORCEPLAN in query analyzer to ON. If I set it back to OFF, query analyzer is much faster.
Any idea how can I obtain the same results with the SP ?

If your SP has any parameters, then declare a local variable for each one. Copy the parameter value into the local variable, and replace the references to the parameter with references to the local variable.

This will eliminate the "parameter sniffing" phenomenon, which is supposed to improve performance, but in many cases has opposite results.