Although I haven't cleaned any watch parts, I have cleaned a lot of scuba equipment. You need a good degreaser like simple green to clean the grease from metal parts. I use a product called Blue Gold. First clean off all the grease you can with the cleaner mixed to the recommended amount and a clean rag. You might need a toothbrush to get into small cracks & crevices. Then I mix it about 2/3 hot water to 1/3 cleaner. Then drop my parts into the solution, and agitate them. If you have an ultrasonic machine, then that would probably be best for the small watch parts.
You may be able to buy a bottle from a local scuba shop. If they don't use this, then they can probably tell you what they use to clean gear for use with O2. Don't worry if that doesn't mean anything to you, they'll know. And if they ask, just tell them you want to apart Rolex dive watches to make into pens.
But really, any good industrial degreaser should work just fine. That, and a tooth brush.
I would take everything apart and get them ready .. take them to a
jeweler and have him run it in his machine. They have a series of
chemicals it uses.. you put the parts in the basket, turn on the machine
and it pumps in each chemical as needed. I ran a batch through a
local guy.. he charged me $5 and they look like new brass and steel.