I was almost right the first time about straddling a pixel. It seems that there was a change in the default behavior of the shape tool around CS2 or CS3 that changed the "Shap to Pixels" option.
Prior to that version, the drawing tool automatically snapped to the closest pixel, but now you can position the tool between pixels and get the anti-aliasing that we both saw. The "snap too.." is now off by default.
Select the shape tool and go to the end of the tool bar and click the down arrow to open the options. In the options panel, check "Snap to Pixels" . This should make things work the way that you want.
