Tim Hortons for example: Always fresh always Tim Hortons. Earliest known instance of something to that effect?
The East India Company motto from 1698 was, "Auspicio Regis et Senatus Angliae", "By Right of the King and Senate of England".
I don't know if this was the earliest company slogan or motto, but it was pretty early.