I *suspect* that the partition set up is the issue here. From the point of view of Windows compatibility, it may be best to format the memory stick on Windows and just use it on your Mac.
I have had similar issues where hard drives formatted on my Mac are unreadable on my Windows and Linux systems. Linux, which has a richer set of hard drive tools than the average Windows install, was able to tell me that there was no valid partition table on the drive, and offered me the option of correcting that. Once I did, all was well.
So, the Mac may not be setting up the partition table on the device in the way Windows expects, resulting in issues for Windows when it tries to access the memory stick. My advice? Set the stick up via Windows, and then use it with both Windows and Mac as you need.