So what about all those people (I had one this evening) who call me up and then say "This call may be recorded for training purposes"?

I understood that both parties have to assent to the call being recorded, unless you have a warrant or work for MI5 or the News of the World (in which case you can record what the heck you like). Though even so, calls recorded by your n900 are not admissable as evidence in court. (Unless it's a call of your husband to his mistress in a divorce court, I think)