A requirement for the SIP PBX I created for my company was to record all calls passing through it. I solved it by forcing all SIP message to pass through the PBX and to modify the SDP body so the stream passes through it and gets recorded. It works well.
I recently found out that this is not allowed.
Is there any other way to implement call recording and how "wrong" is this in regard to the protocol?
It sounds like you're describing a SIP proxy, more or less a Session Border Controller (SBC). A proxy can modify SDP, though it should be careful in doing so. Typically SBCs will set the media destination to themselves, and proxy the data to the destination. So this is perfectly legal spec-wise (assuming the devices are already coming to your server).
However, "Not allowed" could also mean "recording calls is legally not allowed", which varies a lot state-to-state.
A more conventional way to implement call recording would be to capture the RTP packets on the wire and put them together to create an audio file. There are quite a few tools around to do exactly that and it's even inbuilt into Wireshark.
As far as tweaking with the SDP goes it's definitely not something that is "not allowed" at least not on a technical level. A lot of SIP Proxy's are forced to mangle the IP addresses in SDP when user agents put private IP addresses in them. You'll find most SIP servers out there have some sort of capability in this regard and it's often call NAT mangling or similar.