1. No, they don't. Scheduling without divisions can be just as easy, if not easier. The amount of games isn't changing. The 32 teams/locations aren't changing.
2. Just because it's been done forever doesn't mean it's the best way to do it. Rules and regulations change all the time, as we see with the NBA considering taking out divisions completely - and removing divisions does NOT mean you're taking out the rivalries. In fact, it might give teams to spawn newer, better rivalries.
It would make sense for the other sports to get rid of divisions. They play alot of games. Each team to play a team in their conference 3 or 4 times a year and 2 times against the other conference and it would be fair for everyone. Hell the NBA could get rid of conferences altogether and put the best 16 teams in and that would make a better product. But I don't see how it's fair to compare what happens in a 16 game season to an 82 game one.