Title says it all. menu_rebuild() rebuilds the menu immediately. variable_set('menu_rebuild_needed', TRUE) schedules the rebuild for the next page load.
This means that even if you call menu rebuilding code 10 times, the variable_set way will ensure it's not rebuilt more than needed (which is once).
This improves install performance, where we frequently had menu rebuilds happening multiple times for no good reason.