See this for detailed information on different ways to setup and run app detection rules. There's a section on PowerShell tips towards the end.
Intune - Understanding Win32 App Detection Rules
Intune Custom Detection Script
You probably want to examine the IntuneExtensionMnager.log to get a deeper view of what's going on with the detection. In short, if the detection doesn't work reliably every time, there must be some idiosyncrasy with the PowerShell provided (could try taking off the expand version selection and just rely on the presence/absence of the object itself). For instance, perhaps it picks up some leftover information in the registry which leads the app to believe it's still installed. Or the reinstall operation writes something to a different location on disk, which causes it to not be picked up by the same rule.
The only instance where waiting can help is if you're changing detection rules around a lot and want to be more confident it's picking up your latest changes.
Please upvote and accept this thread as answered if it's helpful, thanks!