This is an update on the solution:
Basically I was doing the right thing and passing the correct codec code (WAVE_FORMAT_MULAW) as Richard suggested.
However, each API call: AVIFileCreateStream and AVIStreamSetFormat accepts a different structure. But not all the fields are relevant for the call, so the rest of the structure has to be filled with zeros before setting each field.
For example:
AVISTREAMINFO aviHeader;
ZeroMemory(&aviHeader, sizeof(aviHeader));
aviHeader.fccType = streamtypeAUDIO;
...
Thanks!