I'm not 100% on the A5 but often the device uses a mic on the back of the phone for recording video. Some like my old U12+ had 4 mics and recorded in 3D sound, so you're device may be using both mics and recording in stereo but only one channel is picking up sound or it may only use that one mic. That would explain why you can hear yourself in videos. For voice recording it may assume that you are looking at the phone and use the mic for handset calls, but this also would mean that the mic is working but for some reason the sound it is getting is muffled. I would venture a guess that if you yelled at the phone, similarly to when you did the voice message, you're callers would hear you. But no one wants to go around yelling at their phone. Lol. Anyway, I think you may have been on the right track with the mic being clogged or dirty. We carry these things in our pockets and bags and they can get stuff in places that seem too small for anything to get into. Not sure how you attempted to clean the mic hole, they are usually just little pin ***** holes but I would try that again. Be careful tho because even though the mic isn't as fragile as the speaker it can still suffer damage if mistreated. My go-to for this would probably be an old tooth brush or plastic bristled brush of some kind and I'd probably take just one bristle and come in at an angle making loops around the outside followed by compressed air, not blocking the hole but blowing slightly into or across it almost flute like in the hopes of drawing out whatever is in there. A pin probably wouldn't give you much angular motion and you wouldn't want to poke the mic.
Replacement mics are usually pretty cheap if you think it's damaged or blown. Then it comes down to DIY or insurance.