Im about to build a website which lists companies offering a particular service. The services these companies provide is strictly legal. The website will offer the ability for users to leave comments about various customers reviewing the service companies have provided - as well as showing gallery content and videos. My question is - do I need the permission from each company to add their company into this website? Technically - to get the website off and running, would anyone advise that I add these companies to the website THEN contact them to say they have been added?
Assuming you live in the USA, you don't need permission from companies to talk about/review their services.
Different countries have different laws. Someone from the UK should be able to help you out a little better.
You sound to be squarely within the fair use or nominative fair use exception to trademark law. To prove nominative fair use, you must show: 1. the product or service in question must be one not readily identifiable without use of the trademark; 2. only so much of the mark or marks may be used as is reasonably necessary to identify the product or service; and 3, the user must do nothing that would, in conjunction with the use of the mark, suggest sponsorship or endorsement by the trademark holder.