As the title says. I find it really weird to see it this way, as I know the OS itself do support it. Even Nexus devices don't have it built in.
On some Android devices, you would even need to root them in order to have call recording.
I know the laws of call recording are different between countries, but still, how could some devices (and even Nokia devices) have this feature, while most Android devices don't?
I think it mostly has to do with both of the following:
A lack of demand for the feature. While a small minority of users may want this feature, most "normal" users probably never even think about it.
The laws in the US regarding recording phone calls are relatively complex. They usually vary from state to state (source). Companies probably do not want to expose themselves to additional liability.
If #1 was to change so that a sizable number of people want this feature, then a company would be more likely to put the effort in to make sure that the feature works legally.
