Diffeomorphic but physically inequivalent spacetimes In the last few years there has been a considerable endeavor in understanding the asymptotic symmetries of quantum gravity on Minkowski Spacetime. This has been tied to a study of the BMS group that unveiled the connection of supertranslations with Weinberg's soft graviton theorem and the gravitational memory effect. See, e.g., "Lectures on the Infrared Structure of Gravity and Gauge Theories" for a comprehensive review.
This formalism has also been the basis for the soft hair on black holes proposal due to Hawking, Perry and Strominger.
In the papers I have cited above and references therein it is very common to see the authors talking about "spacetimes that are diffeomorphic but are physically inequivalent".
Citing Strominger's review (Page 67):

Supertranslations transform one geometry into a new, physically inequivalent geometry, despite the fact that they are diffeomorphisms. To see this, consider a solution where an outgoing pulse of gravitational or electromagnetic waves crosses the south pole of $\cal{I}^+$, and another pulse crosses the north pole of $\cal{I}^+$, both at retarded time $u=100$.  Now supertranslate this solution with a function $f(z, \bar{z})$ that has the property that $f(\text{south pole})=100$ and $f(\text{north pole})=0$.  The new solution now has one outgoing pulse at the north pole only at $u=100$  and  one  at  the  south  pole  only  at $u=200$. The outgoing data are measurably changed by the supertranslation.

The idea that the BMS supertranslations take a solution to a physically inequivalent one is a very important observation because it leads to the conclusion that the classical gravitational vacua are infinitely degenerate. On the quantum theory these vacua differ by soft gravitons.
Now, this whole thing has got me a little confused. When I learned GR I've read that two diffeomorphic spacetimes are to be seem as equivalent. Moreover, diffeomorphisms can be seem as the same thing as coordinate transformations.
Still, Strominger's argument is convincing. Furthermore, let us be clear here about who we are talking about: Hawking, Strominger and Perry are experts in GR. Hawking's GR book is perhaps one of the most mathematically rigorous books out there on the subject, and Strominger is a very renowned Physicist with great experience in gravity and black holes. These guys sure know what they are doing.
So certainly I am the one missing something and my question is: what am I missing? How can a diffeomorphism take a spacetime to a physically inequivalent one?
More precisely: is it just a subset of the diffeomorphism group that should be regarded as identifying physically equivalent spacetimes? If so, what is the criterion that defines "physically equivalent" and "physically inequivalent" spacetimes?
 A: 
How can a diffeomorphism take a spacetime to a physically inequivalent one?

This happens when a diffeomorphism acts non-trivially on the boundary data.

… is it just a subset of the diffeomorphism group that should be regarded as identifying physically equivalent spacetimes?

Yes. These are trivial or  gauge diffeomorphisms. 
The theory of non-trivial diffeomorphisms in gravity goes back to the work of ADM on the definition of asymptotically conserved quantities in asymptotically flat spacetimes. The framework to define asymptotic conserved charges and their algebra was then generalized in several respects in Hamiltonian and Lagrangian formalisms. 
In gravity, “most” diffeomorphisms are pure gauge because they are associated with trivial canonical surface charges. Some diffeomorphisms are however too large at the boundary: corresponding charges are infinite and such diffeomerphisms should be discarded. In the intermediate case, we have diffeomorphisms associated with finite surface charges. The quotient of such “allowed” diffeomorphism by trivial gauge diffeomorphisms constitutes the asymptotic symmetry group (ASG): 
$$
\mathrm{ASG}\equiv \frac{\text{allowed diffeomorphisms}}{\text{gauge diffeomorphisms}}\,.
$$
For a given set of boundary conditions (BCs) one can associate an ASG which preserves the BCs. On one hand BCs must not be too restrictive to allow for sufficiently general and interesting spacetimes. On the other hand  BCs are restricted by the requirement that all surface charges must be finite and integrable. There is no universal method or uniqueness in the construction of BCs but once BCs are proposed, their consistency can be checked.
A: Physical properties depend on the metric, which in general is not preserved by diffeomorphism --- even up to deformation.
Take a two-dimensional example (one space dimension and one time dimension):  All two-dimensional toruses are diffeomorphic, but there are an infinite number of such toruses with essentially  different Lorentzian metrics (where "essentially different" means that the metrics can't be deformed into one another).    These metrics have different implications, for example, for how many times your  light cone rotates when you travel around a non-contractible circular path.
