Hello tyreguy -
Over what time period did you notice the change in temperature? Unless it was quite gradual, I'd be sceptical of the limescale theory. Have you noticed reduced flow through your hot water taps at the same time? Limescale will often crust up round the hot water takeoff at the top of your cylinder, and if it's extreme then you may well notice poor flow (I once saw exactly this, about 5 yrs ago).
I agree with 'masona' that scale will mean your cylinder takes longer to heat up. Is your heating timer running all the time or just for an hour or so? Leave it going and see if you eventually get hotter water. If so, then your stat. etc is probably OK and limescale does sound reasonable. Otherwise turn up the stat if you can and see what happens.
By the way, I am only a DIY plumber, but I would be surprised if a professional one could justify £650 for replacing a hot water cylinder (assuming like-for-like replacement with minimal mods to pipework).
As a guide, a new 117 Litre (900mmx450mm outside dimensions) cylinder will set you back around £85, for example from
screwfix :-
http://www.screwfix.com/app/sfd/cat/cat.jsp?cId=101434&ts=18565
Even with new fittings and a new immersion heater, the total parts bill should come in under £100. The last one I did involved a lot of new pipework since it was a totally different cylinder, but it was still done in an afternoon, so it's not a huge job. Escpecially if your cylinder comes from a recognised maker (eg Telford, Albion, Newark) you should be able to go into a plumbers merchant and get an exact replacement with the same tappings in the same places, for direct reconnection.
The way forward depends on your plumbing skills I suppose. There is no cleaning product I'm aware of to de-scale your cylinder, so the best you can do is try to sense-check what your plumber is telling you.
Personally I would drain the cylinder and remove the immersion heater. Especially if it's top-mounted, this gives you a nice big hole through which to shine a torch and inspect the primary heating element (heat exchanger coil inside the cylinder). This would at least allow verification of the theory of limescale. The snag there is that, especially if you DO have limescale, and depending on how old the cylinder is, you may well be unable to remove the immersion heater without damaging the cylinder anyway. You would also need to remove the heater electrical connection and borrow a suitable large immersion spanner.
If you're not confident to tackle the job on your own, I'd certainly get a few more quotes, and ask to see the parts and labour broken down
