A temp agency. You know these kinds of agencies seem to be all over the place. They never seem to find jobs. They seem to exist to profile people and find as much information on them as possible, prodding and poking in to private lives with the promise of a job. There are a few of them out there that I trust because they have actually put me in front of a hiring manager.
I think what is going on is list creation. These companies are probably looking to sell you name to someone else, and probably not even for employment purposes. I almost find it hard to believe that a company could seriously have a policy of not hiring someone based on non business impacting personal issues.
Smokers don't just take random breaks when they feel like it. There are all sorts of products that contain nicotine that have nothing to do with smoking. Clearly the stigma around nicotine is the smoke, second hand smoke, and smell. Testing for nicotine can also turn up people who just ate things like eggplant, red peppers, tomatoes, or potatoes.
By the way, the swabs don't test for nicotine. They test for the metabolite, cotinine. The chemical has a half life of about 20 hours. If you want to pass the test, you could just stay away from nicotine for about a week.
Probably once you pass the test, as long as you don't smoke before the job or during breaks, and as long as you don't smoke in your house, they will probably never know about your nicotine usage.