As described, the OP would be talking about an original, big frame Vaquero with a two digit serial prefix and I agree that you don't see many of either the birdshead or the regular gripped Sheriff's model and $500 would be about what you could expect to pay for a real nice one.
I have an example of both the blue/CCH and a stainless birdshead gripped Vaqueros in 45 Colt and both were very late factory "clean-up" guns that I bought new in 2009 and 2010 via Davidsons. My two examples have serials 58-989XX and 58-994XX.
I have been seeing similar ones at gun shows recently but they are the all blue New Vaqueros with the three digit serial prefix in 45 Colt. I've been on the look out for a New Vaquero stainless birdshead in 45 ACP to partner up with my stainless New Vaquero Montados in 357, 45 Colt, and Sheriff Model in 44 Special.