Ask the DBA for the code and the plans please. Without them there's minimal chance that we can help you.

Have you tried with recompile and is the overhead unacceptable? I've used it on heavily used procs before without problems.