For associative solution you could do the following:
With NX open programming, access all the features in the file read their parameters, and write them into NX4, and thus build the part in NX4.
This is not a 100% solution for several reasons:
1. You cannot create feature that was introduced in NX5/6 in NX 4 e.g. The new holes, New Assembly constraints.
2. Due to changes in NX it is possible that a specific feature cannot be created although its type is supported – maybe due to bugs fixed in NX, or newer version of Parasolid.
3. It is possible that some features do not have API to read/write.
All these problems have some kind of programming solutions:
1. In some cases new holes can be mapped to old holes.
2. For unsupported feature, you can try to create geometry feature(non parameterized), and to add it somehow to the part without deleting parameters of other features, e.g. instead of 3 face blend introduced in NX7.5 you can create geometry equal to the geometry of the 3 face blend, and patch it to the body, without loosing history of other features.
As you can understand this solution is not simple, and requires a lot of effort, but it is feasible.
I hope this helped (at least in theory if not in practice ;-) ).
If you have any other questions regarding this solution you can contact me at: txl@transcendata.com.
Tomer