Looks like its a bug in pytorch that ignores output_padding argument (should be translated into padding for convolution descriptor). @colesbury ^^.  Convolution descriptor that’s being passed into failing cudnnGetConvolutionBackwardDataAlgorithm call has 0 padding, whereas it should have 1 (here’s ltrace for the failing call, followed by ltrace for the passing one for the gradient wrt data for the companion forward conv, they should be the same:
[pid 21910] _C.cpython-35m-x86_64-linux-gnu.so->cudnnGetConvolutionBackwardDataAlgorithm(0xffff7fffffff, { CUDNN_DATA_FLOAT, 0, [ 5, 8, 1, 3... ], CUDNN_TENSOR_NCHW }, { CUDNN_DATA_FLOAT, 0, 5, [ 2097152, 0, 8, 8... ], [ 0, 0, 262144, 32768... ] }, { CUDNN_CROSS_CORRELATION, CUDNN_DATA_FLOAT, 3, [ 0, 0, 0, 0... ], [ 2, 2, 2, 0... ], [ 1, 1, 1, 0... ] }, { CUDNN_DATA_FLOAT, 0, 5, [ 2097152, 0, 8, 1... ], [ 0, 0, 262144, 262144... ] }, 1, 0, 0 <unfinished ...>
[pid 21917] _C.cpython-35m-x86_64-linux-gnu.so->cudnnGetConvolutionBackwardDataAlgorithm(0xffff7fffffff, { CUDNN_DATA_FLOAT, 0, [ 5, 8, 1, 3... ], CUDNN_TENSOR_NCHW }, { CUDNN_DATA_FLOAT, 0, 5, [ 2097152, 0, 8, 8... ], [ 0, 0, 262144, 32768... ] }, { CUDNN_CROSS_CORRELATION, CUDNN_DATA_FLOAT, 3, [ 1, 1, 1, 0... ], [ 2, 2, 2, 0... ], [ 1, 1, 1, 0... ] }, { CUDNN_DATA_FLOAT, 0, 5, [ 2097152, 0, 8, 1... ], [ 0, 0, 262144, 262144... ] }, 1, 0, 0 <unfinished ...>

It is still a mystery to me how it can work anywhere (on Kepler? With 16 planes? deleting ReLU?). Also would probably be a good idea to add deconv test with output_padding, probably there are none now.