I was able to come up with a "no HTML tables required" solution based off of a technique by Stu Nicholls at CSS Play and I personally like it because not only does it work in IE6+ and FF2+, it is also valid CSS that does not require any hacks. For my argument on why a CSS-based layout is preferable over HTML tables, see below.
First, I recommend that when designing new pages with CSS you do it with standards compliant browser mode. For an explanation of quirksmode and standards compliant mode, check out this article from one of my favorite CSS resource sites. All you have to do is add a specific DOCTYPE element at the top of your pages. The CSS will then be forced to render in standards compliant mode, resulting in fewer bugs and browser idiosyncrasies. In the case that you can't switch to standards compliant mode there is a min-width solution for browsers in quirksmode, also available at CSS Play.
Second, you must add an additional wrapper around your existing markup. This wrapper is used to set the min-width for browsers that understand min-width (not IE). You can then use the * html trick to specifically target IE 6 and apply Stu Nicholl's technique to the inner wrappers. The technique is detailed here and the specific example used is "#2 For standards compliant mode IE":
http://www.cssplay.co.uk/boxes/minwidth.html
The end result is rather simple. It creates 2 50% columns using the 2-column ALA style technique mentioned in the original question, that have an overall minimum width (of 500px in this example) where the columns stop resizing and the right column does not fall below the left column. I hope this helps!
Edit: This same technique can be used to apply cross-browser compatible min-width to anything. For instance, the columns do not need to be 50% each and any number of columns can be used. http://www.glish.com/css/ is a great resource for CSS-based page layouts and when combined with this min-width technique there are many nice layouts that can be created with minimal, valid CSS.
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<style type="text/css">
/* For browsers that understand min-width */
.width {
width: 100%;
min-width: 500px;
}
/* IE6 Only */
* html .minwidth {
border-left: 500px solid white;
position: relative;
float: left;
}
/* IE6 Only */
* html .wrapper {
margin-left: -500px;
position: relative;
float: left;
}
.left {
float: left;
width: 50%;
}
.right {
float: left;
}
</style>
</head>
<body>
<div class="width">
<div class="minwidth">
<div class="wrapper">
<div class="left">
Left
</div>
<div class="right">
Right
</div>
</div>
</div>
</div>
</body>
</html>
Now, my incentive for setting up a Stack Overflow account was being able to respond to the suggestion below that "If you want two columns, use a table, rather than trying to force Div's to behave like a table". Since I'm too new to either comment or vote down, I am augmenting this discussion.
Really?
Somebody asks a question about CSS-based layouts and you respond by telling them to use HTML tables?
Let me start by saying that I don't believe that HTML tables are completely unnecessary. In fact, any time I need to display tabular data, i.e. relational data, I use an HTML table. CSS table display properties aren't fully supported yet (coming soon in IE8!) and using a single-level HTML table is an effective solution. Look at the markup for any of Google's web pages and you'll see that they would agree.
As someone who has spent a great deal of time writing CSS-based layouts that are cross-browser compatible when they could have done it in 10 minutes using a table, I agree that there is an easier solution to this problem. However just because you can use dynamite to renovate your kitchen, doesn't mean you should. The following article provides a detailed explanation for why CSS-based layouts are more desirable.
http://www.chromaticsites.com/web-design-blog/2008-04-03/13-reasons-why-css-is-superior-to-tables-in-website-design/