Heterodyne receivers register the sky signal on either a circular polarization basis (where it is split into left-hand and right-hand circular polarization) or a linear polarization basis (where it is split into horizontal and vertical linear polarization). We study the problem of interferometric observations performed with telescopes that observe on different polarization bases, hence producing visibilities that we call "mixed basis" (i.e., linear in one telescope and circular in the other). We present novel algorithms for the proper calibration and treatment of such interferometric observations and test our algorithms with both simulations and real data. The use of our algorithms will be important for the optimum calibration of forthcoming observations with the Atacama Large mm/submm Array (ALMA) in very-long-baseline interferometry (VLBI) mode. Our algorithms will also allow us to optimally calibrate future VLBI observations at very high data rates (i.e., wide bandwidths), where linear-polarization feeds will be preferable at some stations, to overcome the polarimetric limitations due to the use of quarter-wave plates.