Wikipedia lists only a few countries where nodding and shaking are reversed: Greece, Macedonia, Bulgaria and Albania. As a Bulgarian, I can tell you it can be quite confusing for foreigners: I've been living abroad for the last seven years or so, and in the beginning I caught a few puzzled looks when nodding or shaking: my mouth says one thing, but my head apparently another. It didn't take me long to switch to the "correct" way, but when I go back home, I'm sometimes perplexed myself when seeing somebody say one thing and shake/nod in opposition.
Speaking of how to recognize which is which: at least in Bulgaria, there are a few subtle differences which might give you a clue:
- Nodding meaning "No" starts with head going downwards first, while normally one does the reverse. Nodding is also commonly accompanied by slight pouting.
- In shaking meaning "Yes" the head doesn't go left-and-right only, but there's also a tilting motion to the side, i.e. the symmetry plane of the head is tilts with respect to the body, so that the head moves in a somewhat horizontal figure-8 trajectory. This kind of shaking is also more tentative than what one would do for a no-shake.
Generally people would subconsciously understand your nodding and shaking done the "correct" way without a fuss, but you might have problems understanding what they mean by their noggin motions.
Some finger gestures might be helpful (check first which ones are offensive in a given country, you might be surprised). In Bulgaria, thumbs-up for yes and shaking finger (or vigorously shaking head) for no should be fairly unambiguous.