Would convolutional NN recognize patterns in encoded images?
First you should give it a try, because anyone's guess could be off, as there isn't really a complete high level analytic model of how neural networks behave on real data. Most results with neural networks are informed by theory, but involve a whole lot of experimental testing.

I suspect your network might at least learn something from the new images, but would struggle to get anything like the same accuracy as without the noise, because the CNN filters rely on being able to detect similar features at different positions. In your scrambled image, there will not be any meaningful and consistent edges/corners etc that a single learned feature detector could learn to match (and therefore present to the next layer).

A fully-connected network would not have this limitation, and would learn just as well on a set of binary features that have been xor'd identically in each position for each example, as it did on the original copy (i.e. only if the picture was 1 bit depth). It would learn less well if each feature was a scaled 8-bit pixel value that was xor'd with the same 8 bit random number in each pixel position, because that would introduce many more non-linear mappings between input and output. Of course a fully-connected network will generally not learn image tasks as well as CNNs in the first place . . . but if it could learn anything useful at all for your image problem, then it will probably out-perform CNNs after the scrambling effect.

As a CNN usually has a few fully-connected layers, then it may be possible to get something from your scrambled images.


  Thinking logically, the features still exist in the same relation to each other, just in a different form (encoded)


In terms of being recognisable in the way that a CNN filter extracts them, then the features do not exist. That is a problem.