What you could try is create a normal page called companies. Give it a custom page template where you show all the companies.
Download a rewrite class from here: http://www.refactord.com/adding-rewrite-rules-to-wordpress
Put it in your theme's functions.php and put something like this after it and re-save your permalinks:
$options = array(
'rules' => array(
'(companies)/(.+?)/page/?([0-9]{1,})/?$' => 'index.php?pagename=$matches[1]&company=$matches[2]$&paged=$matches[3]',
'(companies)/(.+?)/?$' => 'index.php?pagename=$matches[1]&company=$matches[2]',
),
'query_vars' => array('company')
);
$add_rewrite_rules = new Refactord_add_rewrite_rules($options);
Now on the company page (template) you could link to yoursite/companies/company_name (and not get a 404)
On your custom page tempplate you could test if the company query var is used:
$company = get_query_var('company');
if($company){
// here you test if the company exists
// and show the company info
}
Not sure if this is the best way to go though.