What I think is most likely happening here (without diving into the source code) is that there is a gap between when Magento generates the prices and when it saves it.
Magento stores the calculated prices for products which have price rules applied to them in a special index table, so it can retrieve the prices quickly whenever the price needs to be displayed.
When re-indexing, affected products have their records deleted from the index table and the new prices are inserted. If the re-indexing takes a while as you suggest and customers are still browsing the site, then Magento appears to be falling back to the non-disocunted price (because it has just deleted entries from the index table).
I can think of two ways to work around this. There may be other, maybe even better solutions, but these are the ones which spring to mind immediately.
Run the catalogue price rule indexer at a time no-one will notice the blip in prices, i.e. the middle of the night. Therefore your customers will never even see the price blip. Indexer scheduling can be configured in the admin.
Enable Full-Page Cache (FPC).
If you do this, Magento will cache the entire page, including any prices on it. The cached pages will survive until the end of the re-indexing process, at which point the cache will be refreshed. FPC can have some side-effects, however, so I recommend further research into whether this is right for your situation before you enable it!