Magento – Magento Enterprise: catalog_product_attribute not reindexed on product save

I'm using Magento ee 1.13.0.2 and discovering the next problem:
I have some of the attributes used in layered navigation – color and size. When I add a new product (simple one) and save it – product successfully appears in catalog, however if I click on product's size/color in layered nav – product is not found. If I go to index management page, I see "Product attributes" has mode "Update on Save" and status "Reindex required". If I reindex manually – everything works fine, product can be found by color/size now.

But this is not something I expect – if there is "Update on Save", index should be updated automatically on product save, without manual reindex, right?

Future tests shows me, that Product attribute index becomes "Reindex Required" always, when I save product even without changes..

I tried to debug reindex on product save, and it appears that queries, which fill catalog_product_index_eav, catalog_product_index_eav_tmp tables are all part of one big transaction, which starts on "product save before" and ends on "product save after". Of course, when I debug queries which are generating data for index_eav tables, they return empty results, because product doesn't even exists in catalog_product_entity table…

So, for now I stuck on this, had any one the same issue?