I am personally a fan of the GUID solution, but here is a viable option.
Many solutions to this problem have avoided GUID and used good old integer. This is common also with merge replication situations where many satellite sites merge with a master and key conflicts need to be avoided.
If GUID will not work for you, and you absolutely must have int, bigint, or the like, you can always just use an IDENTITY column and have each table with a different value for SEED. Those datatypes have a very wide range, and it is not too hard to split the range into usable segments, especially if all you want is two splits. As an example, basic int has a range from -2^31 (-2,147,483,648) through 2^31 - 1 (2,147,483,647). This is more than enough for a customer table, for example.
Transact-SQL Reference (SQL Server 2000)
int, bigint, smallint, and tinyint
Example:
--Create table with a seed of 1 billion and an increment of 1
CREATE TABLE myTable
(
primaryKey int IDENTITY (1000000000, 1),
columnOne varchar(10) NOT NULL
)