Let us start by synchronizing our terminologies!
I think the aforementioned “database” of ~3 million entries is really a single table containing those rows. If that is the case, we need to reduce the no. of test cases by trying to synchronize all other tables other than this table. If that works, then we have only got this table to look into. You could then send us the table structure and some sample data ( if not confendential ). We would immediately start working on it.
Please send the table structure, etc to [email protected]