FK Constraints - Causing Timeouts

1

I have a stored proc, that performs and insert via insert... values (...), that results in timeouts (application log) when the CHECK option is on for 2 FK constraints. The table with the PK, has 10 rows, with the below ids (PK). There are 2 cols in the table with the FKs (CreatedBy, ModifiedBy) that have CHECK constraints to the id col in the users table. At first, I turned off CHECK (set to NOCHECK), and problem went away, but I then simply dropped and recreated the FK constraints with the CHECK option ON, and no timeouts for 4 hours now (was occurring every 10 minutes). There are no msgs in the SQL ErrorLog (blocks or otherwise).
Would the gap iun value for the min(id) =1 and the next ID value = 116256 be a suspect ? 116251 value difference ? I cannot find anything, there is no locking, just randomly occurs with insert to table that has the 2 FK constraints to the below ID column (PK). The FK cols are NOT INDEXED. The FK table has ~7100 rows and 8 other FK Check constraints (to other tables PK, not the below). All tables re-indexed < 2% fragmentation, all stats updated, the only other odd thing is UDT for FK column that has same underlying type (INT) as the PK Column, as well as INS/DEL/UPD triggers on the table with the FK..

Users table
col ID Int Primary Key clustered.
PK ID List.
1
116256
116257
116258
116259
116261
116262
116263
116264
116265

2

Significant number of changes happening on the various tables involved? or indexes not recently rebuilt? I would check the fragmentation %age of the indexes. However, this does not sound likely in the "Drop the FKey and recreate and its fine for 4 hours", that sounds more like some sort of caching problem.

STATs getting out of date?

Perhaps more likely: FK is triggering a Stats Refresh and Stats are set to ASYNC (which is the default). I always change that setting to SYNC (the query that triggers the refresh uses the old stats, rather than WAITING for the new stats) (However, that doesn't sound right either: this would only effect the query that triggered the Stats Refresh, the very next one should run quickly)