Planet13 - 6:30 pm on Sep 20, 2013 (gmt 0)
"You must be able to see your link on the page of the domain that is linking to your site. If you can't find the page, it's gone. (not sure why google still counts it though in WMT)."
No, it could be cloaked. It might be hidden from people using a browser, but visible to googlebot.
they could also be in "random" text widgets. For instance, certain blogs might post random blog comments. It may be the time that googlebot swung by a page, they were displaying a blog comment with a link to your site. when you went by to take a look, they weren't displaying that same comment.
"We are just gonna go get new domains that are in our niche and get links."
Are these good sites or bad sites?
If you get links from bad sites, then you are just setting yourself up for a penalty / Penguin demotion.