Thanks for the article tip hadn't seen it. But I don't agree with your conclusion. In fig 1-6, you should look at the last column. Because really the other channel numbers are quite low. Knowing that, the space domain algo, only really has a chance at 3x3 filters which is quite small.
And since they claim fbfft was even faster than cufft, the situation should look even better for fft.
EDIT: And they are about tied in the 3x3, 64 case.
The current trend in convolutional neural networks seems to be moving toward more convolutions with smaller kernels. This year's second-place ILSVRC winner (VGG) is essentially a giant stack of 19 convolution layers with super tiny kernels, sandwiched between nonlinearities and pooling. "To reduce the number of parameters in such very deep networks, we use very small 3×3 filters in all convolutional layers" http://arxiv.org/pdf/1409.1556.pdf
And since they claim fbfft was even faster than cufft, the situation should look even better for fft.
EDIT: And they are about tied in the 3x3, 64 case.