Since there tend to be many more FK records than PK records in your average database structure, the bloat compounds further, impacting performance as it does so.
Wow, thank God someone finally brought that up! I've dealt with this situation before as well with many different "remote" databases synchronizing into 1 central database with... composite keys. The only thing that could be done was to roll our own synchronization app. The central store had to "re-key" EVERYTHING to it's own server ID and then send those keys back out to the remote servers. Fun!