Are they Crucial sticks? I think that's the brand that has two partitions by default, one with an application/drivers (it shows up with a CD icon in Mac OS X). I know that on my XP machine I can't just plug in a flash drive, XP has to find the drivers and everything. If using another brand it goes through the same process the first time around, and can't just be used instantly.
Is this the same with Vista as well? I've never used Vista for more than 20 minutes so I'm not sure. It wouldn't surprise me, though.
If they are formatted to MBR and MS-DOS with Disk Utility in Mac OS X it will work properly in Windows unless something else is wrong.