Evolving Counter-Propagation Neuro-Controllers (CPNCs), rather than the traditional Feed-Forward Neuro-Controllers (FFNCs), has recently been suggested and tested using simulated robot navigation. It has been demon-strated that both convergence rate and final performance obtained by evolving CPNCs are superior to those obtained by evolving FFNCs. In this paper the maze generalization features of both types of evolved navigation controllers are examined. For this purpose the controllers are tested in an environment that drastically differs from the one used for their training. Moreover, a comparison is carried out of results obtained by single-objective and multi-objective evolution approaches. Using a simulated case-study, the maze generalization capability of the evolved CPNCs is highlighted in both the single and multi-objective cases. In contrast, the evolved FFNCs are found to lack such capabilities in both approaches.