>case in point. if it followed logic it would be Belém d<b>a</b> Pará. or de. but do?

Why should it be Belém da Pará? One says "o Pará", so it follows that Belém de o Pará contracts into Belém do Pará. This is the general rule: I come from Brazil, eu venho do Brasil, since one says o Brasil, "o" being the masculine form of the article. Wine from California would be "vinho da California", since one speaks of "a California": de + a -> da, de + o -> do.

Your trouble seems to come from the fact that you may think that because Pará ends with an "a", it should be of the feminine gender, which is incorrect. Although Portuguese adds an "a" at the end of nouns to feminize them, it does not mean that a word which from the start ends with an "a" should automatically be feminine.