It would depend on how the ad is served, I believe, but if it was served from an ad network most likely no.
There are several ways to research your incoming links. OpenSiteExplorer is a great tool for doing this as it will list all of the inbound links that they have found.
Personally I would ask for a list of links that the SEO company generated for you, and possibly keep track of those in a tool like Raven Tools depending on your budget. They could have paid for the links only for them to disappear in a few months.
As a forum owner we get a ton of spam links. Posts generally get deleted by the moderators, but a new tactic I have found is that link builders will register a profile, put the link in their profile, and never post to fly under the radar. While the profile page itself carries very little weight if it comes from a highly ranked domain it will carry some. I bring this up because I am auditing all of our forum user profile links, getting rid of any links and profiles that don't belong there. I would not be surprised if a quarter of all new forum registrations are using this tactic, using Chinese or Indian contractors since it requires human intervention.
The other thing I have seen, which is extremely black hat, is that some SEO firms have had used someone to exploit sites. I was involved in a site where this happened; Our CMS was compromised and the cracker put in some SEO links in the bottom of the page. Upon further investigation I found dozens of sites where this had happened with the same links. Clearly the links were put there on purpose. What wasn't clear to me was which links were bystandards and which ones were clients.
