Hi Jon,
This is Dave from the company that scanned the part for you. I was just checking the boards and found this post. Hopefully I can offer some assistance.
I'm not really a massive MAX user, but a collegue who you didn't meet on Friday is pretty efficient with it.
Here goes:
1) Import your model into Max as mesh, which .stl already is, turning off welding and all other import features. This will import the mesh cleanly, without filling up too much memory.
2) Create yourself a NURB plane using the point surface command. This creates a surface that conforms to the vertices that describe it and is forced to travel through them. I would recommend using fairly low densities of vertices on maybe 3x3 to start with otherwise you'll be doing this forever..!!
3) By turning on vertex snapping and sub-selecting the 'point' options under the modifier list for the NURB surface you can 'SNAP' the vertices on to the mesh.
With a bit of practice you'll be able to build up a patch work or as the pros like to call it 'network' of NURB patches that describe your object. These can then be exported to IGES format and read into Solid Edge. Try and join the surfaces before export as well to maintain the integrity of the model.
From my point of view this is easier done in Rhino, but you can get more or less the same result with MAX, it just takes a bit longer.
Good Luck mate.
Dave