Dropping and recreating foreign keys every three months is not defensible. Recreating the FKs takes just as long time as takes to perform the check for the DELETE.
I suggest that you schedule adding the indexes for the next maintenance window.
[font="Times New Roman"]Erland Sommarskog, SQL Server MVP, www.sommarskog.se[/font]