Almost.

The Omnia HD (S60 v5) cannot. Third party apps like Total recall do not record on that phone.

Yes, I know, I'm nitpicking, but I'm bored.

Now, I don't know about other countries, but in the US, it is indeel LEGAL to record conversations providing at LEAST one party in the active call knows the recording is taking place.

That is to say, either the person who placed the call or the person who received the call.

The law does not apply to Government entities such as Law Enforcement. Such entities have to get a little troublesome (to them), piece of paper called a warrant.