Is anyone doing any table reorganization, or is your application doing any bulk loading of data? A technique in bulk loading is to disable contraints on one or more tables (because of the way the data is organized) so all of the data goes in, and then the contraints are enabled.

For auditing - select one of the tables where the problem is occuring. Write a trigger that records what is happening to the table (row/table, before/after, insert/update/delete - the 12 types available - 2x2x3 options) and then check the status. Check the before and after status of a constraint.