In a number of countries(ie most of the US, UK , Canada and Australia) the law states that you can record the call without telling the other party as long as the call is not disclosed to a third party. This differs in some states of the US. Source: http://en.wikipedia.org/wiki/Telephone_recording_laws

The legalities in certain states and territories is not really an issue and as maemo is designed to be open it should be up the user to either enable an option to tell the other party they are recording or tell the other party themselves.
The more important issue is whether or not this can be implemented in maemo.