It's random, though there are streets where certain cogs like to be. Check in the Players' Guide on the TT home page. I used to keep that up in the background while I played!

If they can be anywhere, try Barnacle Blvd. in Donald's Dock. If they have to be in TTC, just keep looking, and switch districts.
I always say that the simple act of accepting a task for a certain type of cog causes that type to immediately fly away! So for the future - always try to get JUST cogs for a task, even though they will require more of those for the same reward. If the task is not one from a "visit task", you can shop around (Some visits can be avoided, but most can't). Try all the guys in the HQ, and if you need to you can try the ones at the other playgrounds, or the ones on the street, or even random shopkeepers along the way. You will be amazed at the difference in difficulty for the SAME reward! Good luck!