T., when you say that one species predominates and one year predominates, it sounds like the column totals would be high for that one species and the row totals would be high for that one year. But are years in separate rows (i.e. rows are sample unit-year combinations) or are years in separate columns? (i.e. columns are species-year combinations). I'm guessing the former.
In any case, if your data matrix has only a few columns, then it is not surprising that NMS autopilot can't beat the randomization test, because you should be able to get a low-stress solution with any data matrix with just a few columns, even if they contain random numbers. And it is even easier if there aren't very many rows.
It sounds like your matrix may be small enough that you should skip the randomization test and instead focus on getting a low stress biologically reasonable solution.