How to get FK to use new index without restarting the database

Is there a way force the db to re-evaluate its execution plan for a FK
without bouncing the DB?

PostgreSQL 8.1.17

In our latest release our developers have implemented some new foreign
keys but forgot to create indexes on these keys.

The problem surfaced at one of our client installs where a maintenance
DELETE query was running for over 24 hrs. We have since then identified
the missing indexes and have sent the client a script to create them,
but in our testing we could not been able to get postgres to use the new
index for the FK cascade delete without bouncing the database.

Here is an example of an added fk but missing index....

ALTER TABLE scheduled_job_arg ADD CONSTRAINT sjr_scheduled_job_id_fk
FOREIGN KEY (scheduled_job_id) REFERENCES scheduled_job (id)
ON UPDATE CASCADE ON DELETE CASCADE;

Thanks in Advance,
Eric