Как правило, замедление происходит в случае, когда вр. табл. используется(delete, update) в той-же процедуре, где и заполняется и вызвано оно тем, что сервер строит план запросов _до_ заполнения вр. таблиц.
Если таблицы большые, необходимо это дело разнести.
Например:
create proc1 as
create teble #temp(...)
create index ... on #temp(...)
exec proc2
exec proc3
go

create proc2 as
insert #temp
.....
go

create proc3 as
update #temp
.....
delete #temp
.....
go

Если таблицы маленькие, то не знаю...