Replication fails because of a non-existent foreign key

Sorry for waking up this dead thread, but I hate it when questions remains inconclusive. Anyway, I had the same problem. Apparently SQL server replication saves foreign keys in "dbo.MSsavedforeignkeys", which is where I found my blocker FK. A quick delete dbo.MSsavedforeignkeys where constraint_name = N'FK_TableOnlyInDestDB_MyReplicatedTable' solved my problem. Of course, there may be more "best practice" ways of cleaning up after failed replications.

As Aaron noted, SQL Server does not invent objects, so it has to be somewhere.

My initial thought is that you are pointing replication at a different database than you think you are. Check in the "Subscription Properties" dialog what database was used to create the subscription.

Also check what type of replication you are using. If it is any of the bidirectional forms it might try to apply that breaking change to the publisher.

If that does not help, check your default extended event session to see what was actually executing when the error was raised. See http://www.brentozar.com/archive/2013/08/what-queries-are-failing-in-my-sql-server/ for details of how to do that.

That should allow you to figure out what is going on.

If after all that you are sure you are in the right database and replication is still tripping over the non-existent FK, I can only recommend to drop the subscription and maybe also the publication and start from scratch.