Can you provide us with more information about your settings?
Do you use options combinations?
Do you use setting track with options?
Do you use quantity selectbox?
If you use options - now they are recalculated at server side with help of AJAX requests.
No option combinations not used on the product in question.
Yes, there is tracking with options
Yes, use quantity select box
Further to the original post - the problem is seen on the product page only, on the category listing page when an out of stock option is selected the "add to cart" button is replaced with "out of stock" - which is what I would expect to see on the product page.
Hope this clarifies for you.
With regard to the ajax is there anything we can do to improve the speed?
EDIT* Have just tried with option combinations on - same problem.