“Gaping holes in the data” and “not enough data” is far from the same thing (*) 
Pitching up can result in aliasing, if high frequencies in the signal gets over
the limit X/2 (**) (X being the samplerate). Pitching down can not result in aliasing.
Also, aliasing isn’t necressarily assosiated with pitching anything up or down,
it’s a characteristic feature/problem of all sampled signals (not only audio).
An example of aliasing that I believe everybody has seen:
In a movie you usually have about 25-30 pictures a second.
This is indeed a samplerate! The difference from a movie to audio
is that you have a whole picture each frame instead of just one
samplevalue (per channel) in audio signals.
When wheels (ie on a car), or something else, rotate faster than 25/2 = 12.5
(ie X/2 in my post above) rounds per second, you will see the wheel
spinning backwards and/or at a different frequency than the original
wheel turned. This is aliasing. The name “alias” comes from the property
that one digital signal can have come from more than one real signal,
in other words: the digital discrete signal does not contain enough
information to uniquely identify how the original signal really was.
For example will a wheel rotation of 1 Hz and 26 Hz show up as 1 Hz
in a movie with 25 frames per second. 1 Hz and 26 Hz is thus alias
frequencies.
The same thing with audio, with 44100 Hz samplerate (frames per second),
original signals of 100 Hz and 44200 Hz will both result in a 100 Hz signal
in the digital sampled signal.
(*) There are many aspects to digital audio that’s is very complicated and
mathematical. There are lots of “intuitive” explanations around on the net,
and lots of people who “knows for sure” whatever they’ve read in a tutorial
written by a 14 year old boy who heard it from a friend and wrote it down
without understanding a word of it. Don’t trust the net. Be paranoid. 
(Of course, then you shouldn’t believe me either…)
() X/2 is called the “Nyquist frequency” from the mathematician who
proved () this property of discrete (***) signals.
(***) Which is actually not very complicated to do.
(****) (*****) “Discrete” signals are “sampled” signals, ie a sequence of
numbers, as a contrast to “continuous” signals such as exists in the real
world. Your soundcard converts between digital, discrete, signals and
continuous analogue electrical thingy.
(*****) This is the last footnote. Promise.
Most of what you wrote was actually as I understood it, except for the “can’t alias pitching down” bit - was unaware of that, but it seems to make intuitive sense.
