If someone were to start using a trademarked company name with the word 'not' in front of it would it infringe their trademark?
e.g. a company is called 'foo' and their name is trademarked and another company comes along and calls itself 'not foo'.
Possibly yes, in some circumstances. True, all trademark cases naturally hinge upon specific "circumstances". Here are some that may be relevant.
The central question in trademark infringement is whether the junior user's brand "creates a likelihood of confusion" with the senior user's goods or services. There are numerous factors that may go into the legal analysis of a particular case, primarily the similarity of the brands and whether the goods or services are in "related" markets.
Another factor is how distinctive the brand was prior to adding "not".
Technically, however, each brand is "evaluated as a whole", and something with the word "not" added to it might be ruled clearly distinguishable from the one without. This may direct the inquiry toward other factors.
In addition to "infringement" as "confusingly similar", you may also need to be aware of coat-tailing ("free-riding") on the fame or reputation of someone else's existing brands, even if there is no likelihood of confusion with the senior brand. In the EU, for instance, there are rules allowing Member States to enact laws allowing trademark owners to prevent others from using a similar brand where
"use of that sign without due cause takes unfair advantage of, or is detrimental to, the distinctive character or the repute of the trade mark."
EU Trademarks Directive 2008 at EUR-Lex
Also worth noting that business names are regulated differently from trademarks and it may be normal to have a business name registered in one place while someone else has the identical name registered to them in a different place.