Flush rewrite rules deletes the option that stores the rewrite rules, then calls the method that regenerates rules and saves it back into the option. If this option is not empty, the rewrite rules will always be loaded from the option. This is because regenerating rules can be an expensive operation, so it should only be done when something changes.
Adding rules on init doesn’t result in extra database queries, it’s actually the correct way to add rewrite rules and the only way to be sure your rules will always be present. The cost of adding a rule is just some simple string and array manipulation code which adds your rule to the array stored in the rewrite class for the life of the request. If something else flushes rules and your rules aren’t added on init, they will disappear. If the option that stores rules is empty, the rules will come from this array when it’s repopulated.