Foreign Key Constraint Set Back to Trusted
Will the optimizer recognize the change and consider them before using cached query plans for re-run transactions? Put another way, do I need to consider removing any query plans?


Yes, the optimizer should recompile the plans since changes to an underlying table are one of the triggers that result in a plan recompilation. Since checking a constraint involves an ALTER TABLE command,

ALTER TABLE [dbo].[table] CHECK CONSTRAINT [fk_table]


this should qualify it as a valid reason to update the plans, according to this TechNet article (from 2008 R2 but should stand true for current versions as well) which specifies that a ALTER TABLE or ALTER VIEW command will qualify. 


  Is it safe to say this is a situation where SQL Server has been
  rebuilding the index (we do have this turned on), and maintaining the
  index throughout inserts, updates, and deletes, but simply not using
  the foreign key?


Correct. As you've observed the optimizer ignores the foreign key when creating query plans - no operation involving the table will make use of the foreign key while it is untrusted, whether that is a rebuild or an insert, update, etc.