No, they can not. Once your CID is banned, it cannot be unbanned. Some games such as GTA 5 can temporarily ban your CID. First time offense on GTA 5 will get you a 2 week ban.
I can't say it's completely normal, what firmwares have you used and been online with? I've had same cid for over two years completely fine (other than game bans).