If we do get a 49-49-2 Senate

[Verily]

ok, here's one: if they didn't caucus and it was two totally independent senators?

They'd have to negotiate. 49 Republicans + Cheney still doesn't make a majority vote for things like President Pro Tem and Majority Leader; the Republicans would need one of the Independents, and the Democrats would need both (as they have).

[Verily]

OK, so  if the whole senate votes on majority leader, do they also vote for minority leader? If so, why didn't the GOP elect Ted Kennedy to the role?

As I understand it, each party votes on their own party leader within their caucus, and then the full Senate votes between the two for the role of majority leader, with the loser of that election becoming minority leader.

Out of curiosity, why do they bother with the full Senate vote?

There haven't always been two parties. Think Unionists before the Civil War, the Farmer-Labor and Progressive Parties during their heydays, or the Era of Good Feelings when there were no real parties.