When working with velocities close to c, one should be working with four vectors,
In special relativity mass is not a conserved quantity. It uniquely defines quantum mechanical particles by the length of the four vector describing them called the rest mass, or the invariant mass, characterizing each particle, invariant under Lorentz transformations.
The term relativistic mass and its algebra has fallen by the way side , exactly because it causes confusions as the one in the question. It connects Newtonian inertial mass concepts with the relativistic energy concepts and is useful only when thinking of spaceships and the fuel they will need to reach relativistic energies.It is not used in particle physics.
Suppose the two particles you are assuming are elementary particles of the standard model of particle physics.They cannot "stick together" inelastially, because energy would not be conserved as you state in the question. The experiment has been done several times, in e+e- scattering, and there is no channel where at the center of mass a single entity forms/sticks together, except within the Heisenberg uncertainty principle, resonances as seen here:
Note the peaks as the energy of the beams increases, these are resonances, with the necessary mass for conservation of energy but decaying very fast into their constituent elementary particles, within the HUP. For a Δ(t) they make up a new massive entity , which has to decay into standard model particles because they are resonances. This is the experimental fact, and lorentz transormations describe it exactly.
Now in nuclear physics, if a stable state could be reached in the passing over the resonant part of the potential, it would be stable but not completely inelastic because there is no just "sticking" in quantum physics. There will be other particles taking away kinetic and binding energy ( the sticking part in quantum regime) as in this example of fusion in the sun. Proton proton fusion will always give a deuteron which has a mass lower than two protons, and thus at least a positron and an electron neutrino leave the interaction region balancing the energy budget. Note that also quantum numbers have to be conserved, hence the positron electron neutrino pair.