I am not so sure that it is flawed, provided you don't need the machine to appear at exactly the right time. You write your note asking for the time machine to reappear at 12:32. Years, decades, even centuries pass and your note either does or not make it to its destination.
But from your point of view only a few moments have passed. There is nothing to stop you from trying again with another note or another means of communication.
Imagine standing outside a post-box at 12.32 precisely. You need to get a message to someone in the future to tell them to send the time machine back at 12.32. So you quickly write a letter to Bill and chuck it in the post box. If the time machine appears instantly, you made a good choice. If it doesn't you write a second letter to Ted and throw that in the post box. Wait a few seconds. If that doesn't work you send a letter to someone else ...
Now here's the bit that's frying my noddle right now. Do you have to wait for the postman to come and empty the post box? If so, why?
When you say it like that, it doesn't seem flawed at all. In terms of Bill and Ted, they actually send the messages to themselves by thinking them (Let's just tell ourselves now to send the machine back to now, and hope we don't forget) and then the machine appears. They use it on other things, such as keys and traps.
Of course if you send a message to someone, as you explained, and the machine doesn't arrive you try again. Although there is still a chance that the machine could arrive on time from a letter you haven't sent yet, which could cause a paradox (the machine arrives before the letter is sent, and if the hero jumps in the machine without sending the letter, the machine can't be there because no one could send it back because they never got the letter etc. etc.)
I do enjoy the mind-f**k that comes with time travel