I was just reading in Chip and Dan Heath's "Made to Stick" about how to get certain ideas to stick. I read about an anti littering campaign that used the "Don't Mess" slogan.
Then the crazy thought hit me… What if that ad campaign was the origin of the phrase? I googled it and amazingly enough, it was! There is even book on the story of the slogan!
As pointed out in Made to Stick, the "Don't Mess" ads were some of the most successful ever. They reduced littering by 72 percent and have become synonymous with Texas itself.
Here is some more info.