Part of your problem may also be the ifs ands and buts. For instance, if you have done business with the company or a partner in the last year they can call you. This is reeeeally vague. As an example, I work for MCI who owns the 10-10 numbers (10-10-220, 10-10-987) so we can call anyone who has used those numbers in the last year, even if they are on the the national DNC list. We are partners with American Airlines, so we can call anyone who has done business with them in the past year. Also, most contest you sign up for say in the fine print that you will be added to a call list...yep can call you then too. Check to find out if your local phone company sells out your number as well, many do...and it's completely legal because you agree to it in the fine print when you sign up for phone service.
Another reason it's important to add yourself to the NATIONAL DNC list (as opposed to just the state) is only people calling from that state have to comply with that list...most people don't know that. For example, if you live in Kentucky and are on the Kentucky DNC (not even sure if Kentucky has one, but this is just an example) and I live in Pennsylvania...I can call you, because I'm calling from PA and don't have to comply with Kentucky's do not call registry.
While you're waiting for the 3 months to pass before they update the registry, when you do get a telemarketing call you should ask to talk to a supervisior, tell them you want on their do not call list especially if you're less then plesant...because if you're a dick to me I'm gonna schedule a callback at 6pm (when more people are eating dinner

) (If you ask for a sup, your name will definately be put on the list, heh) Be aware, that's not going to stop the company from calling you right away either, as it takes up to 10 business days for your number to be completely removed from the OS.
Good luck tracing the call, sorry I couldn't be of more help when it comes to that. heh