When it comes to the time complexity of problems, the encoding of the problem can be totally crucial. In general, the encoding of the problem cannot be separated from the complexity of the problem itself.
The first canonical example of this (as mentioned before in answering another question) can be seen with the following two problems:
(1) Given a deterministic Turing machine $M$, string $x$, and integer $k$ written in binary, does $M$ accept $x$ within $k$ steps?
Problem (1) is $EXPTIME$-complete. However the following problem is $P$-complete:
(2) Given a deterministic Turing machine $M$, string $x$, and integer $k$ written as a string of $k$ ones, does $M$ accept $x$ within $k$ steps?
So already, the way in which $k$ is represented in an instance completely determines the complexity of the problem. (Note if I wrote $k$ in ternary, $4$-ary, etc., problem (1) remains $EXPTIME$-complete.)
Another interesting example comes from circuit complexity. Consider the following two problems:
(3) Given a truth table of $2^n$ bits for a function $f:$ {$0,1$}$^n \rightarrow ${$0,1$}, return a circuit with AND/OR/NOT gates that computes $f$ and contains a minimum number of gates.
(4) Given a function $f:$ {$0,1$}$^n \rightarrow ${$0,1$} represented as a circuit with AND/OR/NOT gates, return a circuit that also computes $f$ and contains a minimum number of gates.
Problem (3) can be easily seen to be in $NP$, since the minimum circuit for $f$ needs at most $O(2^n/n)$ gates, and checking that a given circuit works for $f$ takes $2^{O(n)}$ steps. However (3) is not known to be in $P$, nor is it clear that it's $NP$-complete. The curious status of (3) is discussed in
Valentine Kabanets, Jin-yi Cai: Circuit minimization problem. STOC 2000: 73-79
What about problem (4)? It is not known to be in $NP$! It is known to be in $\Sigma_2 P$ of the polynomial time hierarchy, but not known to be complete for that class. However the version where you use the representation of formulas instead of circuits is known to be $\Sigma_2 P$-complete under Turing reductions:
David Buchfuhrer, Christopher Umans: The Complexity of Boolean Formula Minimization. ICALP (1) 2008: 24-35
Examples of this sort are everywhere in complexity theory, simply because the encoding can really matter if the relative sizes of encodings (or the complexities of encodings) are different enough. Luckily, most "natural" encodings (for which there are polynomial time mappings from one encoding to another) do not seem to affect the overall complexity of a problem (e.g. whether or not a problem is in $NP$). This is another reason why the notion of polynomial time is one of the main focuses in complexity. It is a "robust" notion that isn't affected by whether you use e.g. adjacency lists versus adjacency matrices to represent a graph in your graph problem. Related to this, there is a recent and thought-provoking reference that outlines a complexity theory for succinctly represented graphs (graphs whose adjacency matrices are the truth tables of small size circuits):
Sanjeev Arora, David Steurer, Avi Wigderson: Towards a Study of Low-Complexity Graphs. ICALP (1) 2009: 119-131
Finally, concerning your proposed "isomorphism-respecting" encoding of graphs: while it would be very neat to have, it would not be considered natural, since we don't know how to efficiently obtain such an encoding from any of the other encodings that have already been deemed natural.
UPDATE TO ADDRESS YOUR REVISED QUESTION: I think it is a neat idea to try to study "problems" as classes of languages that "represent the same thing" in some strong sense. I'm not aware of significant prior work on this (other than the cheap reply that "all NP-complete problems represent the same thing", which I don't think is what you are driving at). The closest reference I can think of is a related attempt to define "algorithm" in a similar way. See Blass, Dershowitz, and Gurevich's cool paper: http://research.microsoft.com/en-us/um/people/gurevich/Opera/192.pdf
