This is one of the few cases i would prefer using custom database tables since you are talking about lots of records (10,000 – 100,000) and since Custom post types use the posts table which will hold many empty fields in the case you describe.
But i guess there is no right or wrong way to do that and it’s a matter if opinion since a good (correctly) configured MySQL database can handle a lot more then a few 100,000’s records without a glitch.