eBay is not the only source but I suppose it is the biggest. You do have to be patient. There are a number of sellers with buy it now prices 4 or even 5 times what auctions for the same lens close for. Do your homework set your price and realize you will not win them all and that is OK since there will be another auction next week.
It has taken almost a year but I now have a 20, 24, 28, 35, 50, 105, 120, 135, 150, 200, 300 and 400 all Super-Multi-Coated Takumar. I still want an 85mm but they are expensive. And maybe someday a 17mm/4 fish-eye.
As someone pointed out earlier not all M42's are cheap but unless you want something specific I cannot think of a less expensive way to put together a full kit. If you are willing to use manual focus and manual exposure. You can also use Av exposure with some adjustments on many M42's. For a basic kit (35mm, 50 or 55mm and a 135mm) you can probably get all three for $100 - $150 if you are careful.
I have not touched a k-Mount in 3 months now, I went cold turkey on M42's by finally removing my kit lens from my bag.
Check out the
Takumar Club for a good discussion on using Takumar M42 lenses.