Do we have options other than deleting the rows that reference non-existing foreign records and add a foreign key constraint to the table so that we can remove the @NotFound annotation?

You don’t have to delete the rows. You can simply set the FK column to null. There even is the option for a foreign key to configure on delete set null in case you don’t want to do that in your app, see e.g. the PostgreSQL documentation https://www.postgresql.org/docs/current/ddl-constraints.html#DDL-CONSTRAINTS-FK