Hi Nahush Dandekar,
I had faced a similar problem when I was designing the product RPM Meter. (RPM->Rotations Per Minute).
I have 3 suggestions for you:
1. What language are you using for writing the code: C, assembly, etc.
If it is "C" then there are chances that you are missing certain interrupts. It will give better results if you use Assembly language for atleast the Interrupt Service routine.

2. Do your calculations very very thoroughly, because one slip of a step and your whole product starts giving problems like these. Remember when you are using the V-F convertor, think particularly of the border line conditions, where the voltage is near 0 V or 10V. Refer to the various graphs shown in the datasheet. Particularly for Frequency output versus PowerSupply Voltage, Temperature, etc.

3. Check the ground paths of your PCB. If there is improper grounding then this is typically what will happen. In such a case I think Kai (and many others on this forum) will guide you about the grounding techniques.

And please treat the V-F as an ADC; Apply similar design rules of the ADC to V-F.

Bye,
With best regards from,
Mr. Kiran V. Sutar.