Double the "speed", double the frequency? Usually, when some sample is played-back at twice the rate it was recorded, the pitch of the recording sounds an octave higher. 

For example: $g(t) = \sin(2 \pi f t)$ and $g(2t) = \sin(2 \pi f 2 t) \implies \sin(4 \pi ft)$. Where $f$ is a given frequency.

There are some strange "sample" cases however that when played back at twice their recording rate their pitch appears to...not have changed as expected. And some even stranger "sample" cases that when played back at twice their recording rate their pitch appears to be...lower!

How do these strange "sample" cases might "look like" (in terms of a mathematical description) and what are, broadly, the conditions that can lead to such cases?

EDIT (hint 1):

Variants of the technique of pitch-shifting / time stretching have been mentioned so far by more than one persons in relation to this question. 

Pitch shifting is not the core of the question and the technique of pitch-shifting does not change the nature of the question.

As it was pointed out in one of the comments to this post and as a form of a hint: Yes, pitch shifting does alter the pitch of the "sample" but a) what sort of sample would sound almost identical to its unshifted version if it was passed through a $2 \times$ pitch shifter and b) what sort of sample would sound at a lower pitch if it was passed through a $2 \times$ pitch shifter. (the $2 \times$ here is just an example).   

EDIT (hint 2):

Another two things that have appeared in responses so far are aliasing and some aspect of human hearing. In other words, "Maybe you have pitch shifted in such a way that the frequency jumps back on to itself" and also "Maybe you are taking advantage of some psychoacoustic phenomenon in which the frequency has changed but the perceived frequency does not"

Aliasing and the limits of human hearing are relevant to this question but are not absolute requirements for the "paradox" that is mentioned here to occur.
White noise: sounds exactly the same if you play it back at double the speed
Stack up diminished fifth starting at a low enough fundamental (say 20 Hz). Play back at double speed: sounds exactly the same.
Stack octaves with equal amplitude starting with a low enough fundamental. Play back at twice the speed: sounds exactly the same
Detune the octaves slightly (say multipler of 2.05 starting at 20 Hz). Play back at double the speed: perceived pitch goes DOWN.


You get plenty more when fiddling with the harmonic structure. 
Code example for the last one:

%% make some disharmonic sounds
fs = 44100; % sample rate
q = 2.05; % harmonic multiplier
f0 = 20;  % fundamental
n = 10; % number of harmonics
duration = 2; % length of file at fs
nx = duration*fs;
t = (0:nx-1)'/fs; % time vector
x0 = sin(2*pi*f0*t); % fundamental
f1 = f0;
for i = 2:n  % add harmonics
  f1 = f1*q;
  x0 = x0+sin(2*pi*f1*t);
end

x0 = 0.5.*x0/max(abs(x0)); % normalize
% and play
sound(x0,fs); pause(duration);
sound(x0,2*fs);