well, there's really no such thing as a "BRAND NEW" trans anymore.
They're all REMANUFACTURED, either performed by the manufacturer (best) or
by a 3rd party transmission specialist. The manufacturer who produced the
trans for the e39 stopped producing these transmissions right at - or shortly after - the time
BMW stopped making e39's.
And imo, I'd get a remanufactured transmission ready to install instead of having a shop rebuild it. Businesses that do nothing except remanufacture transmissions have better quality control and better test methods than an independent garage that's going to tear it down and put it back together in the corner of their shop.