Don't know why you couldn't replant trees then. There are many types trees that do well in saltier soil. For example, White Ash, Red Cedar, Black Walnut, Japanese Black Pine, Pin Oak and Red Oak. Doubt it'd take much to get something estabilshed, and it'd probably take over on it's own gradually.
It would be futile. Native Samphire, melaleucas and casuarinas can live in saline soil conditions that would kill most anything non-native. There may be exceptions of course.
Its when the Samphire starts to die that you know your in shit street.
In the long run, it would probably be wise to introduce a profitable salt-sequestering crop into regular rotations, just to keep marginal lands from becoming unfarmable.
Native Australian trees are the most salt-hardy trees on the planet. The non-native species you listed would most likely not even survive in "normal" Australian soil conditions.