Why not have a proxy database that EF can rely on PKs?

You could map from the proxy database to the 'real' database (via whatever PK vodoo you doo).

Or perhaps have surrogate keys in addition to PKs-that-EF-can-rely-upon for your strange usage...

'Routinely changing PKs'... I'm not sure I want to know why... sounds quite desperate.