Thanks for all the information here.
We have decided that "dumb" solids will be enough, no need for the history tree. If we need modifications, then rework the part, but that's what we decided.
What we are going to migrate is models of snowmobiles, so big assemblies, that includes all kind of parts (few big and complex "plastic/design" part, lots of sheet-metal parts, and a big bunch of everything else). Typical amount of parts inside those assemblies would be between 500 and 2000.
Concerning the NX product, I could already have a seat installed, as UGS promised to I-DEAS customers the "free" migration, but it would require way too much work (database clean-up is one "small" part), knowledge and actually also to pay something (Oracle related cost for the Teamcenter, the data management for NX). Also I've been following the development of the product, and they are still not garantying the full "integration". It seems some data are still not working.
I've contacted Theorem already, and we run some tests, but some parts (typically the "plastic" parts) needed to run with the translator twice, with a special setting applied the 2nd time if I understood correctly. So that was not a "great" solution IMO.
STEP is also an option we consider here, but we might hit some difficult parts that won't export (I have seen few of those already) and then we are in trouble...
I'm now more and more leaning towards buying the service, of course with the "warranty" that the data will work so it would minimize the work we have to do here.