There really is no 100% guarantee that balloons will spawn every n4th and n9th minute. Those are just the spawn times.
The Nook's Cranny dialogue trick is done to guarantee the spawn.
By the way, it's not just the first 10 minutes of the hour. It's every 5 minutes (for example 01:04, 01:09, 01:14, 01:19, etc). So you can shoot a max of 12 balloons per hour.
Also, balloon direction changes at night. So if it's not coming in from the east, check west.