Is the ground of your circuit tied to the parallel port ground? They
must be tied together for this to work.

Yes. The ground rail on my breadboard is connected to the parallel
port ground as well as the negative terminal of my power supply (AAA
batteries.)

Change your VCC supply to +5V. Although the HC165 can handle +6V, it
is at the high end of the spec. In addition, with a 6V VCC, the
logic output high level is too high for TTL inputs.

~5.6V is actually supplied -- is this really too high? The port seems
to be able to read individual 1's and 0's this way (I poked around
with other parts of the circuit.) If it was just a matter of it being
too high, I would imagine that it would simply cause problems on the
parallel port side. But as it is, the 74HC165's internal state seems
to be corrupted (because removing the connection while shifting out
bits does not ensure that the succeeding bits are correct.) How can
out-of-range voltages cause this bizarre effect?

I can try breaking down the voltage to 5V using resistors but that'll
have to wait until tomorrow evening when I can get the supplies.

Are there any other possible causes?

One thing that came across my mind was that if a 1 appeared on the
output pin, some interference would somehow cause the clock signal to
pulse (even though they're physically not very close.) If you look at
my schematic, I'm only writing the high nibble whereas the low nibble
is always 0xF. An extra clock tick would cause 1's to be shifted in,
hence 0x5 turns into 0x7 and 0xA to 0xF but it doesn't explain 0x4
turning to 0x3 or 0xC to 0xD. I guess the only thing I can think of
now is that the internal state of the 165 is somehow being corrupted
by the interaction of the Q7 output pin going high and the parallel
port (note that the parallel port itself is not forcing the line low
or high, I've tried test that.)