I too have witnessed the uncanny ads, but not even from my own phone (I don't have Facebook on my phone). A friend mentioned a particular restaurant I have never been to, been near, or searched for.
I can only assume my friend's conversation was geo-tagged either by my phone (android, no non-system mic access), or the data was combined on the server end to place both of us at the same place / same time, and used his recording to market to me.
I'd also like to note, the 'amount of bandwidth needed' is almost nothing by today's standards. Not to mention it can wait to transmit that data until on wifi. 8khz audio (telephone quality) is just kilobytes per second. A reasonably unsophisticated algorithm could trim the audio for an highs and lows (IE, statistically, sound below or above some dB threshold is trimmed because it won't be useful) and uploaded. We're talking about just a few kb per conversation.
Of course, the Facebook app is a memory, storage, and cpu hog (IMO), so I don't think it's unreasonable that given today's modern phone hardware some word recognition software may be present on devices themselves.