I haven't been for a long time, but was during the heady days of the dot.com boom. If your job is in high demand and pays reasonably well it will happen. They often get your number and name from other people at your workplace, I know some recruitment agencies effectively ran 'spies' within companies - occasionally taking them out for meal/drinks as a thank you. Sometimes phone lists get handed to these people, or they wangle their way through reception to speak to 'someone in IT' (as an example) then get passed around.
Believe me, Sales people (which they are) will find you if they want to. I wouldn't be too paranoid - ask them how they found you if you are worried. Are they a reputable recruitment firm?