Merging Data from Multiple DB

Hi,

I am working on a application and I need some advice on the data warehousing
aspect of it.  The situation is like this:  I have an application that will
be used at each one of my branch offices.  Each branch office is autonomous
and each has its own instance of the db.  There is currently no interaction
between branches.

However, I need to do centralized reporting.  This means I need a way to
merge all the data from the branches into the HQ central data warehouse.
Obviously, there is a hugh problem with duplicated primary keys.

For performance reasons, each branch must has its own database and a
centralized transactional system is not an option.

I was considering just centralizing primary keys generation, but that seems
very slow too.

Segmenting primary keys among the branches is doable, but it is too much of
a maintainence nightmare.

What do you suggest?

Thanks.