I was going to suggest Kong, too. My mom has had four dogs, over the span of over 30 years. All of them have been chewers. Most of the toys we've gotten for them have lasted a week, tops. The Kong we got for the first dog, meanwhile, is starting to show slight signs of wear.

I have no idea how they make those things, or what they put into the recipe, but whatever it is, it works.