It's normal behaviour for any software to make a Start Menu shortcut, that's what the Start Menu is for. However if you choose to remove it, removed it should stay.
What operating system and service pack is this?
That said, for those who want to remove all such shortcuts, we Mods thought that they had long since fixed that issue along with the reappearing desktop one.
I suggest contacting Technical Support and asking for escalation if necessary.
It's free and available via the link under Useful Links at the top of this page.