clearfix should contain the floating elements but in your html you have added clearfix only after floating right that is your pull-right so you should do like this:
<div class="clearfix">
<div id="sidebar">
<ul>
<li>A</li>
<li>A</li>
<li>C</li>
<li>D</li>
<li>E</li>
<li>F</li>
<li>...</li>
<li>Z</li>
</ul>
</div>
<div id="main">
<div>
<div class="pull-right">
<a>RIGHT</a>
</div>
</div>
<div>MOVED BELOW Z</div>
</div>
Happy to know you solved the problem by setting overflow properties. However this is also good idea to clear the float. Where you have floated your elements you could add overflow: hidden; as you have done in your main.