Classification in general is far less affected (badly) by outliers than is ordination. MDS is based on a regression (between input associations and reduced space associations). Non-hierarchical classification should not be unduly affected by outliers. PATN should identify an outlier and this ‘group’ should only attract objects that are closer to it than any other group.
Not sure what Monte-Carlo process you are referring to.
The non-hierarchical process in PATN v3+ uses random seeds (see the help for the complete process). While this sounds odd, it works fine in practice. In the DOS version of PATN, you could use any seed file.