How About Just a Regular USB Headset for Skype?
Somewhat similar to the OP's request for a mini-USB headphone for their cell phone, how about a small headset with a USB connector (not a mini-RCA plug) that will work with Skype on most third-world internet cafe's? I've seen cheap bulky USB headsets and expensive (over $30 USD) small headsets), but nothing that's both small and cheap.