How where your sliders positioned at each of these stages?
I also play with the technology setting at "Very Fast."
Try it on normal. The reason being: Research screams at Very Fast, but your production rate is unaffected, or rather, constant with respect to the same number of turns on other tech rates. Between discoveries, on Very Fast, you do not have time complete planetary improvements, particularly labs, but also production improvements, which can contribute to research via focusing. So playing on VF, you discover stinger when when you have only had time to build two basic factories and are now expected to produce medium sized ships with stinger, with crappy facilities, while the AI is building harpoon ships with better facilities. Meanwhile, the AI has a production bonus (a small one, on painful) and trades all these techs, and using this bonus builds research buildings proportionally faster, and now you are in trouble. YMMV, but this is what I have found.
Every game I have ever played has had tech trading, tech brokering, and tech stealing. My feeling, without knowing precisely the math, is that the production bonus that AI's get after Tough has a magnified effect when the tech rate rises.
I think this is how it works, but I may very well be wrong:
Let's say that on normal a tech takes 10 turns to research and on VF it takes 5. I build 10 research labs. During that time, other civs each build 11. Now, no matter the tech rate, labs produce 6TP each. But when the tech requires 1/2 the TP, that 6TP contributes *more* than a 10% decrease to the time of discovery, because the TP output remains constant, but the number of TP required decreases. I.e., because the AI gets a production bonus, he builds the extra lab, which by itself is an advantage, but contributes more than 10% increase in research speed, because the research TP required is less.
Beyond this, you might look at your maintenance costs for your planets. You may be allocating a lot of money to research, but because your maintence is high, you start going broke to maintain the high pace of research. One thing I've learned is to resist the temptation to build planetary improvements until you absolutely need them. Don't just mindlessly plop down factories or morale structures unless you have something important for them to always be doing. Remember that instead of building 10 basic labs, you can build 5 and time your research so that by the time the 5th is built you have just researched xeno labs and all those labs now upgrade. This saves 1/2 your tiles. Time your research so that social improvements come at the right time to save you from building out, as opposed to "up". It is not uncommon for me to have colony with nothing built for 20 turns, and it is much better to have a planet with three invention matrices than 10 basic labs, when maintenance and the opportunity cost of lost tiles is factored in.
Finally, always keep your research slider precisely adjusted so that no research is wasted up the ladder if you don't want to research the next tech, i.e., move the slider until it stands above the cusp between x and x - 1 turns, where x is the number of turns you want it to take. You don't have to be very anal with this on Painful but when you get to Maso and Obscene not doing this is quick death. It doesn't increase your research speed (except indirectly), but it ensures that any spending not needed for research is sent to production without waste. That means e.g. constructors take 1-2 fewer turns to produce at the same research rate, which matters.
Another tip: I'm not above going for the occasional cheap tech, but you should curb this tendency and stay focused on what you want from the next tech. Always have a good justification for what you are researching, the weakest being time.
There are hundreds of strategies, and the game does require some experience and skill. For example, research diplomacy techs and you will get more money for your trades. On the other hand, spend too much time researching diplomacy and other areas will suffer. Getting the balance right, here and elsewhere, is the fun. Of course, there are players here who shoot right up the diplomacy tree, but they are able to anticipate and adjust to the consequences, because it is part of grand, well-justified plan.