I don't know how long devastation takes to disappear, but if enemy armies are always coming and going on the same spot then don't expect it to disappear for a while.
As for expansion on VH-VH: Bridges and highly defensive positions are your best friend. Lots of provinces are separated by rivers that have a bridge or two over them. If you park an army on a bridge like this for a few turns they'll spill devastation into the enemy territory, and the enemy will inevitably throw wave after wave of men at you. Just hold the line with a few phalanxes, a couple archers and a couple calvary and you'll hold forever. Wait a few turns for their armies to fizzle out and then hit their city hard. Regroup, retrain, find a new bridge, and repeat.
Also, the AI has a tendency to leave cities almost entirely without garrison every once in a while. This happens particularly when they have a big army in the province, but not necessarily right next to the city. Get some spies out and keep an eye out for this. As soon as it happens, load an army into a boat and sail over to take it. If you have ballistas or onagers then you can take the city in the same turn. Often from there the AI will pull back its forces rather than try and retake the city. If you time it properly you can wait until the enemy's big stack is halfway in between the cities, and then take the next one in the same manner.
It's also important to get into a rhythm with the computer. Usually they'll hurl a few big stacks at you at once, and then start building again. You have to start hitting their cities as soon as that last army of theirs dies. If you wait too long, they'll just build back up again. If you attack too soon, you'll have to fight your way to their cities. Good luck.
Who are you playing as btw?