Usar city.companyname não é menos "ruim" do que seu domínio usando .local. Ambos são TLDs não reservados e nenhum de vocês deveria usar qualquer um deles.
Dito isso, acho que você está latindo na árvore errada. Nenhum destes deve ser um problema, o seu problema provavelmente está em outro lugar.
Will raising the first domain (CITY.COMPANYNAME) to 2003 domain and forest functionality levels be ok with it's odd name?
Sim.
Could the odd naming be what is causing my difficulties in creating the trusts?
Não.