I went to bed grumbling about Dewback troopers and my spouse came up with this idea (likely to shut me up).
Since we don't see the Empire use beasts of burden anywhere else, assume the Dewback troopers were an anomaly. Something the local forces came up with. Tatooine is a backwater that probably doesn't get resupplied regularly and they added Dewbacks as a necessity. When Vader shows up, they activated the local Stormtroopers to hunt for droids.
I like this explanation because it structures beasts of burden in the Empire as an exception. While Dewback Troopers is very Star Wars (can we put a crazy creature in the scene? Do it) it does not feel very Imperial (Heavy emphasis on mechanized everything. Why did they put that AT-AT in a jungle for God's sake). I get the impression that if the Empire needed hound dogs it would build a "sniffer" droid.
I don't know if I'd go with there being 'local' stormtroopers on Tatooine. However, Vader's stormtroopers commandeering Dewbacks from local farmers/traders/whatever and putting them to use in their scavenger hunt seems very likely.