If you have separate tables for 'company' and 'contact', you shouldn't have a problem, as long as it is clear (on the html forms the user is actually interacting with) whether the intent is to add a new company + contact, vs add a new contact with an existing company.
When you're adding another contact to an existing company, you simply don't INSERT anything into the company table; the contact table gets a new row added with the company ID being set to the ID of the company.
I'm assuming a table structure something like this:
create table company
(
id int auto_increment,
name text
...
);
create table contact
(
id int auto_increment,
company_id int, // references company.id
name text,
phone ...
);
This design assumes that a company can have any number of contacts, but each contact relates to exactly one company.