If you are paginating this then you are going to be running multiple queries anyway. The usual way is to get the count first,as you say, and then to run the query for each page using a LIMIT clause; and this should apply to the first page of results as well as all the rest.
(first, your query in a legible form)
"SELECT c.company_id, q.region_name, c.firstname, c.lastname,
c.title, c.company_name, c.address, c.company_email, c.areacode,
c.phone1, c.phone2, j.country, i.industry
FROM smi_companies As c, jupiter_countries As j, smi_employer_industries As i,
smi_regions As q, smi_company_regions As r
WHERE c.company_name like '%$q%' And j.country_id = c.country_id
And r.company_id = c.company_id And r.region_id = q.region_id
And i.industry_id = c.industry
GROUP BY c.company_id, c.firstname, c.lastname, c.title, c.company_name,
c.address, c.company_email, c.areacode, c.phone1, c.phone2, q.region_name,
j.country, i.industry
ORDER BY c.company_name";
Now, as it should be written (and I'm sure Sxooter agrees)
"SELECT c.company_id, q.region_name, c.firstname, c.lastname,
c.title, c.company_name, c.address, c.company_email, c.areacode,
c.phone1, c.phone2, j.country, i.industry
FROM smi_companies As c
INNER JOIN jupiter_countries As j ON (c.country_id=j.country_id)
INNER JOIN smi_employer_industries As i ON (c.industry=i.industry_id)
INNER JOIN smi_company_regions As r ON (c.company_id=r.company_id)
INNER JOIN smi_regions As q ON (r.region_id = q.region_id)
WHERE c.company_name like '%$q%'
GROUP BY c.company_id, q.region_name, j.country, i.industry
ORDER BY c.company_name";
Much easier to take in at a glance. Of course, the simplified group by is mysql specific.
Now nowhere in all of that is there anything to indicate the city? Unless it is the c.address field. So I'm just going to use that in the count query you need to setup the pagination
"SELECT company_name, COUNT(address) AS city_count
FROM smi_companies
WHERE company_name like '%$q%'
GROUP BY company_name, address
ORDER BY company_name";
That will return each matching company once, with the count of different addresses for each company, hence the count of cities. So the num-rows will give you your result count to print to the user and your total results for the pagination. You store that in a session var in the usual way, along with the query string I hope.
If you also save the city_counts in a session array you can use them to also control the pagination so that you do not get orphan cities at the top of a page. I'll leave that to you to work out how you do that.