Data representation affecting problem complexity
Although not (yet) getting all the way down to $\mathsf{P}$, Group Isomorphism and other algebraic problems can depend heavily on the format of the input, in a way that is far more subtle than merely padding. For example, when the groups are given by multiplication tables, there is a trivial $n^{\log n + O(1)}$-time algorithm to test isomorphism. When the groups are given by generating sets (say, of permutations, or of matrices over finite fields), there are slightly sub-exponential algorithms, but the problems are at least as hard as Graph Isomorphism. When the groups are given by generators and relations, the problem is undecidable (indeed, when given by generators and relations, even telling if the group is trivial or not is undecidable, whereas this particular task is trivial in the other mentioned formats).

Another algebraic example is provided by Grobner bases. Most questions about ideals in polynomial rings become comparatively easy if you're given a Grobner basis for the ideal instead of an arbitrary generating set. But computing a Grobner basis is $\mathsf{EXPSPACE}$-complete. (This is perhaps not as good an example, since it is a property of the input, rather than a the format of the input that is affecting complexity here. But I thought I'd mention it anyways.)