Best way to do the record is with a "pass-through" device, where you plug the recording device where the headset plugs in, then plug the headset into the recording device, which will pass the call through and allow you to on the phone while you record it.
Such a device can be built at home with a few parts from Radio Shack and a personal digital voice recorder. Yeah, I know exactly how to do it. Perhaps at some point I'll put together a tutorial for it, but currently too busy with my children to think about it. Perhaps after school starts back I can consider it.
About the legality of the recording... Yes, many places in the world it is illegal to do so in many countries, and some allow you to do it at will. It really gets tricky when you cross country lines, or when you cross state lines in the USA. In the USA, each state has their own set of laws about allowing/disallowing recording of calls.
There are laws that require 1 party consent, 2 party consent, etc. With one party consent, at least one party in the conversation needs to approve of the call being recorded. I happen to live in a one party consent state. With 2 party consent, you need 2 parties to agree, even if on a conference call with 20 people. There are also "all party consent" places, where everyone being part of the conversation must agree.
If you live in a one party consent state and call a 2 party consent state, you must inform the person you are calling that you are recording the call and get their permission. Get the permission on the recording, or it isn't legal. If permission is denied, you must turn off the recorder.
Because of the complexities of the laws, and because of frivolous law suits such as a woman suing McDonald's for the coffee being too hot when she tried to put the cup in her lap and remove the lid to add sugar and creamer, burning herself in the process, and she won a million dollar law suit, well, these types of things will make a company not want to take the chance on it coming back on them.
Also, by forcing an apps access to the microphone to be denied when a phone call is in progress, it prevents malicious apps from recording calls and sending them to another location on the internet without the owner's permission. It's called protection of privacy, which Android simply does not offer like this.
Personally, I'd rather have the assurance of privacy, and use an external tool to record the calls.
These topics about call recording seem to come up pretty often, as no one actually does a search before making a new post. If you do, you'll find it answered many, many times already. I'm definitely going to need to put up a tutorial about how to make such a device after school starts back. Perhaps I'll even build a few and offer to sell them to those who are not inclined to electronics work.