I think the source of my confusion was not knowing that regular expressions in perl always start matching from the left side. If the regular expression could start matching from anywhere, then using the non-greedy modifier could give the behavior I was expecting in my original post, i.e. matching "bar".
This is not a Perl-specific issue. The "Leftmost" rule is one of the features of a NFA-based regular expression engine, which includes Perl, PHP, Python, and most other commonly used regular expression implementations. So now that you're aware of it with respect to Perl, you've learned something that can be applied to most other languages that implement regexes as well! :)