What kind of softener do you have? If its the magnetic kind, then it will make the hardness less inclines to stick but as you have found, it will stick. If its the osmotic kind that actually removes the hardness then its not working right!! We have two loos, one is fed straight off the main with unsoftened water and the other one is upstairs and fed off the tank which has softened water in it. I never need to descale the upstairs one despite living in a super hard water area.
Stuff like harpic does work but as it works by chemical action, once the bit you put on has dissolved all the limescale it can then it will stop working and you need to rinse and add more. If its built up then you might need to do this a few times before its all off. I am a bit of a wimp about using stronger acids, so prefer to persevere with a weaker one. Once the scale is off, daily treatment will keep it off.