Have you tried updating to the latest version of the SDK and lowering the adv interval?
We describe this problem in more detail here:
Dealing with many onExit/onEnter events
We’re also working on optimizing our SDK further to minimize these issues, so keep an eye on our GitHub (https://github.com/Estimote/Android-SDK/releases), but there’s only so much we can do, b/c the very root cause here is that some Android devices are simply quite unresponsive. (In which case lowering the adv interval should help a ton.)