Yes, radiator blockages aren't unusual and I'm surprised that no one, myself included, hasn't mentioned this as a possible cause of your problems. There are "potions" that you can use to clean out the cooling sydtem but they rarely work on bad blockages. You can take the rad out and back flush it with a hose i.e. from the bottom to the top and see if that helps. You'll see if a lot of scale comes out but it's unlikely to clear all of the tubes. An old established radiator shop can remove the tanks and rod out the core and then rebuild it if the core is in good condition, but a new core shouldn't cost a lot more than having it cleaned out. Labour charges will be similar. The original rads were efficient enough for pretty well all climates including very hot ones but modern cores don't seem to be quite as good, less copper perhaps. Consider having a new core with an extra row in it if you are in a hot area.
Talk to the rad shop and get a quote for work then go back and flush the rad and see if you can save the money! New rads are available, and aren't too expensive if you can't get the work done locally.
There's many here that have been through this routine so don't think you're the only one who's had this problem.