Is there a GUID alternative for distributed key generation?

If data from multiple tables comes to one central table and you need to address changes to these records then my suggestion is to use two columns as PK of you central table. One column could be the Identity field from clients (not unique) and one column could be a client code (not unique) assigned by you to your client apps. The aggregate from ID and client code will be your PK

This solution has the advantage to not require any changes on the client side apps (perhaps some identity code to send to your central server where you could use for some security measure)Of course, if the customer base grows (hopefully) you need to keep a centralized table of code assigned to each client. The search on the central table should not be a problem because you are using two numbers (or short string for the identity code).

You can always just add a PK column that is a number, and (depending on the DB you are using) setup a sequence or identity to handle it.

You could also create an index over the multiple columns your currently have to help speed up your searching.

You could implement a key table.

Basically, the key table is just a table with one record: the next available integer key. When your program needs to generate a key, it increments the key in the key table. It has now reserved the previously available key. It can assign that key to whatever it likes and will be assured that it will not conflict with any other key pulled in the same manner. This is how the LightSpeed ORM works by default. Its benefit over using the built-in identity column is that you can assign item ids before inserting them to the database, and therefor can define item relationships before inserting all items at once.

If you're worried about conflicts, you can lock/unlock the key table before reading and incrementing the next available key. If you know you need to insert more than one item at a time, you can increment the key by that much instead of by one multiple times. If you are guessing that sometime in the future of your application you will need a certain number of keys, you can reserve a block of sequential keys, and keep track of them internally. This may possibly waste keys if you don't assign them all, but prevents excessive calls to the database.