I know very little about the E36, but I know it is not really all too far off from the E46. If it says you need a specific O2 sensor for a '99 E36 M3, I would trust that.
I do not know exactly which location it is, but I know it is post-cat. If i were you, I'd check E36 forums. If nothing comes up, I'd unplug the wires from the post-cat sensors and see if "Probe 4" comes up for a secondary error (probably something along the lines of 'Lambda Probe (# here) Signal not plausible'). If you get a matching number, then you know just which one it is.