Two of the same lens should be matched well enough. I have three different stereo cameras, and two of them are hardly "precision matched": I have an ancient 127-format camera with two simple meniscus lenses, and I have the new Holga stereo with a pair of Holga lenses. Both are perfectly capable of forming decent stereo photos. If anything, I find that stereo improves the performance of a given lens, as your brain combines two separate low-resolution images into one image that appears to have more resolution.
The bigger problem with stereo images occurs when the exposure is not exactly the same between images; our brains don't like seeing the same image with two different brightnesses.
Agreed with all of this. I too shoot with the Holga Stereo and have noticed the "increase" in resolution (even though technically there isn't any) when the two images are merged into one by the brain. And yes, the brain doesn't like it when the two images aren't matched or in sync...it struggles to put the images together but can't, which becomes frustrating. Thus, I would steer away from tilt...too much room for things to go wrong and mess up the 3-D effect, IMHO.