I recently paid $19.95 per month for an incoming link from a certain site. They claim a certain number of visitors per month. Is there any way i can get a fairly accurate traffic count on someone elses website? Alexa.com will only tell me "Not in top 100,000", which doesn't tell me much.

Did you not ask for proof of the stats in their media kit?
I am sure they will have no problem showing if it is legit. Have you asked them?

In order to say this they should be able to provide analytics data that backs their statement.