Restricting possible permutations in Graph Isomorphism problem
It's GI-complete.  Here's a simple reduction.  Let $G_0,H_0$ be any two connected, undirected graphs on $n$ vertices.  Consider the vertices of $G_0$ as even-numbered vertices of $G$, and add $n$ odd-numbered vertices that aren't connected to anything. Construct $H$ from $H_0$ similarly.  Now $G$ is vertex-pair-isomorphic to $H$ if and only if $G_0$ is isomorphic to $H$, so solving vertex-pair-isomorphism is at least as hard as solving graph isomorphism.