Is it OK that SameQ considers expressions identical, although they have different structure?

The problem is that SparseArrays are "atomic". Mathematica is getting more and more atomic expressions with each version. There are good reasons for this (mostly performance), but it can also get problematic because there are many operations which need to be defined (i.e. what makes sense) and implemented separately for each kind of atomic expression. Sometimes this implementation is done in a not fully consistent way. The discrepancy between SameQ and Depth is one example.

I think that finding the best way to handle each atomic expression is not at all an easy task. SparseArray has certain behaviours only because it represents an array, for which operations like e.g Length make sense. Thus enacting general rules, like "every atomic expression has Length 0" would be counterproductive. Some inconsistency is probably unavoidable.

What complicates matters more is that many complex atomic objects do have a compound expression representation, which will usually immediately eveluate to the atomic version. These representations are typically used for serialization—writing to text files (Save), sending through MathLink, Compressing, etc. See this post on how to get this representation reliably. How visible these representations are during normal use varies. Some will show up with a simple InputForm.

In principle, there can be a disconnect between what an expression represents conceptually, what its compound form looks like, and what its true internal representation is. In practice, there probably is a disconnect between them. For example, think about Graphs. It isn't even obvious when two graphs are conceptually the same. Should that mean isomorphism? Should it mean that they are identical as labelled graphs? Should it mean that they are represented with identical data structures? It is not very well known that Graph can have multiple different internal representations (sparse array, edge list, ect.), which are completely transparent to users. There also seems to be some internal caching going on with certain graph computations (e.g. possibly with layouts), which again isn't exposed at all to the user.

This is not an answer, just a long comment. I made this comment because some might read your question as a complaint—"something obviously isn't right". But I just don't see how it could be made to work in a way that everyone would agree is correct.

We need not turn to anything as complicated as SparseArray to see the same behavior.

a = Rational[1, 2] &
b = With[{s = Rational[1, 2]}, s &]

  (*  Rational[1, 2] &  *)

  (*  1/2 &             *)

a === b

  (*  True              *)

Structurally these are equivalent, but in one case the structure is unevaluated and in the other it is the external representation of an atomic internal format.

I learned to doubt "sameness" from the answers to my Stack Overflow question:

• Instability in DeleteDuplicates and Tally

As WReach wrote: SameQ Is Not An Equivalence Relation

A more trustworthy comparator is Order.

Order[a, b]

  (*  -1              *)

The function System`Private`VerbatimSameQ that you discovered is not a solution, at least in version 10.1.0. Instead it appears to just be SameQ with a HoldAllComplete attribute. Evaluating a and b gives the same "True" result as SameQ:

System`Private`VerbatimSameQ @@ {a, b}

System`Private`VerbatimSameQ[##] &[a, b]

  (*  True              *)

  (*  True              *)