Лучше всего всегда очищать ваши поплавки. Сразу после того, как вы закроете div с помощью класса .right, и как раз перед тем, как закроете div с помощью класса .container, добавьте новый div, например:
<div class="clear"></div>
.clear - это просто {clear:both;}
в вашей таблице стилей. Это то, что я использую весь день, и работает как удовольствие.
Окончательная разметка будет:
<div class="container">
<div class="left"> ... </div>
<div class="right"> ... </div>
<div class="clear"></div>
</div>
Редактировать: Точно так же, как ваш последний пример, по-видимому. :)