Foreign key of multiple tables
You have couple options. I'd describe one I like the most, but you can find others searching for 'resolving polymorphic association in database'.  Add a common table for companies and contacts (I'd prefer to rename contacts to people or persons), say party. Thus, companies and contacts will have FK to party. Then you add link table party_address(address_id,party_id) with FKs to addresses and party respectively.

UPDATE
For instance (I know it's oversimplified, normally you may have different address_type, address change history, etc, but I guess it illustrates idea). 

Note: enum is used because mysql still doesn't have check constraints. Unique constraint on (party_id, party_type) added so child tables can have a foreign key references to it; thus, optional relationship implemented and enforced on database level- Party can be either Person or Organization; no way it can be Person and Organization at the same time.

  CREATE TABLE PARTY (party_id int not null auto_increment primary key,
party_type enum('person','organization') not null,
CONSTRAINT UQ_PARTY UNIQUE(party_id,party_type));

CREATE TABLE PERSON (party_id int not null primary key, 
party_type enum('person') NOT NULL DEFAULT 'person',
....
CONSTRAINT FK_PERSON_PARTY FOREIGN KEY(party_id,party_type) 
 REFERENCES PARTY(party_id,party_type));

CREATE TABLE ORGANIZATION (party_id int not null primary key, 
party_type enum('organization') NOT NULL DEFAULT 'organization',
....
CONSTRAINT FK_PERSON_PARTY FOREIGN KEY(party_id,party_type) 
 REFERENCES PARTY(party_id,party_type));

CREATE TABLE ADDRESS(address_id INT NOT NULL auto_increment PRIMARY KEY,
.... );

CREATE TABLE PARTY_ADDRESS (party_id INT NOT NULL, address_id INT NOT NULL,
CONSTRAINT PK_PARTY_ADDRESS PRIMARY KEY(party_id,address_id),
CONSTRAINT FK_PARTY_ADDRESS_PARTY FOREIGN KEY (party_id) REFERENCES PARTY(party_id),
CONSTRAINT FK_PARTY_ADDRESS_ADDRESS FOREIGN KEY (address_id) REFERENCES ADDRESS(address_id));