Digital Microphones and PICs

[JonW]

Prob still an AMR codec that was developed in the late 90's for GSM.  Other military codecs can compress further but are not available in the public domain.
At its highest compression setting, AMR-NB operates at 4.75 kbps. Converting to kilobytes: 47,500 bits / 8 = 5,937.5 bytes ≈ 5.9 KB.  Prob slightly more with silence breaks etc.

Another issue is whether you could code the AMR standard in a cheap MCU. The Nuvoton audio recording chips are super cheap—less than a standard 8-bit low-end PIC!

[Fanie]

what will be the bare minimum bytes size of a voice message of 10 seconds over a digital channel?

You can probably get away with a very small digital message to the point that you cannot recognize the person's voice and the message.  Try it with Audacity (it's free, and the best audio editor), you can adjust the sound quality in it.