[dba-SQLServer] Slow Sprocs

I have an SQL2000 database with a number of tables.  I have a second 
database which has a number of identically structured tables (but 
with different data) as well as tables with data that is used by both 
databases.  Both databases are on the same server.

In both databases I have a number of sprocs that join data from their 
unique data tables and the common tables.  The sprocs work fine in 
the database that the houses the shared tables.  However, the sprocs 
in the database which doesn't house the shared tables run very slow 
(for example in the second database a sproc may take 15 seconds to 
run, while on the first it might take over 5 minutes).

What are the things I can do to speed up the sprocs that are pulling 
data from the other database?

Combining the databases into one file is not an option as for company 
reasons they require the data separate.
Repeating the shared tables in each database is not an option as this 
would double up the maintenance required to update the data.

Regards

David Emerson
Dalyn Software Ltd
Wellington, New Zealand