I checked out the game you mentioned, and the mouse speed was identical in both cases for me. I believe that the issue you are experiencing isn't that mouse-speed in fullscreen is inherently faster or slower than windowed, it's that directX based fullscreen modes don't apply the desktop pointer speed adjustments.
When I tried adjusting the mouse speed, then I saw effects like what you were describing (control panel -> mouse -> pointer options, see attached image)
I like fast mice :)
I think this might actually be why you are seeing a problem. I'll be blunt, you are a freak. Your freakish pecadillo for responsive pointer movement puts you in a very small category of people for whom Microsoft has not designed for with DirectX. If you want the pygame "problem" fixed, I suggest you file a disability discrimination lawsuit against the DirectX developers.
Or you may use openGL through pygame. OpenGL fullscreen should use the mouse the same way that windowed does, so the pointer speed stuff is applied in both cases.
Attachment:
PointerSpeedDialog.PNG
Description: PNG image