I'm about to start the Tabata routine to increase my cardio endurance.
The best I've found is this calculator.
Are those results accurate? If not, please suggest an alternative.
They are accurate as far as they go, but they are rough estimates at best.
VO2 max is a measurement of how much oxygen you are actually using at maximal exertion. The only way to accurately measure this is by using specialized equipment with a mask that captures all exhalations, and then measures the amount of oxygen and carbon dioxide that is being exhaled to calculate how much oxygen you are actually using. Check with your local university/college kinesiology programs, some of them offer VO2 testing, or if you have a local triathlon/endurance coaching center, many of them offer VO2 testing for anywhere from $50 - $200 US dollars.
Also, VO2 max is really more an indicator of potential than it is anything else. You can raise your VO2 max by doing nothing more than losing weight, since part of the calculation is based on body weight. Say you have a 220 pound (100 kg) man who has a VO2 max of 50ml/kg/min, or a VO2 max of 5 liters (5000 ml). This man does absolutely nothing except diet to lose 44 lbs, so he is now at 80 kg. His VO2 max is now 62.5. You're not any more fit, you've just lost weight. (This is a somewhat simplistic example, there are other factors that go into this in most cases.)
You could try the Cooper test, which is basically "run at a steady pace for 12 minutes and look at the table". I've always found it sufficient for my purposes (to see how much I improved in a given time period).