We have two lasers in the lab which have (quoted) "random polarization". These are the uniphase lasers labeled 1103. Details found here:
Under the stock number NT64-103 (reproduced below):
Beam Diameter, 1/e2 (mm)
Beam Divergence (mrad)
Minimum Output Power, TEM00 (mW)
Longitudinal Mode Spacing, Nominal (MHz)
RMS Noise, 30Hz - 10MHz (%)
Laser Class - CDRH
Diameter of Laser Head (inches)
Length of Laser Head (inches)
There is also a PDF for the uniphase lasers in particular found here which gives more specific details about the structure: http://www.photonicshop.co.uk/fe/Pdf/JUHeNeLaserHeads_1100Series.pdf.
To remedy this, Zach found a laser with 1103P (the P specification is plane-polarized) and seems to be working as we expect now.