In this paper we consider the optimum detection of OFDM (Orthogonal Frequency Division Multiplexing) signals with strong nonlinear distortion effects. It is shown that the optimum performance with strong nonlinear distortion effects is not as bad as one might expect and can even be better than the performance with conventional, linear transmitters. To achieve these excellent performances we should employ receivers able to take advantage of the information associated to transmitted data symbols that is inherent to the nonlinear distortion component, in opposition to traditional OFDM implementations where nonlinear distortion effects are regarded as an undesirable noise-like component. We study the achievable gains of the optimum receiver both analytically and by simulation. Since the complexity of optimum receivers is extremely high when we have nonlinear distortion effects, even for OFDM signals with a small number of subcarriers, we propose several sub-optimum receivers and evaluate their performance. Our sub-optimal receivers allow remarkable performance improvements, being able to reduce significantly the gap between the optimum performance and the performance of typical OFDM receivers.