That's an interesting response from the council.
I'd be inclined to write a gentle note back, thanking them for their information and in a cunning way, try and replay what they said to you, back to them.
It's more than someone's jobsworth to get them to put it in writing, but if you are cunning enough, you should be able to get effective 'clearance' that 'its up to you, pal'.
Legally I don't understand it - if you live on a relatively modern estate - one where all the land wasn't developed and then a developer did the business on the whole site, the ownership of the land got split between the individual parcels for the houseplots and 'the rest' which essentially became adopted as part of the public highway. The public highway includes the footpaths and verges. In some situations, part of the developed land can become part of the formal council ownership - parks, for example.
So I conclude that if this is just a strip of land between your fence and a footpath, is is probably technically part of the highway.
Nevertheless, if they say it's OK, best get that chainsaw revved up quickly.