I verified that this is still an issue in both Spring '09 patch 1 and also Summer '09 :-(

Good news is that I do have a workaround for this - the key is to use a custom component using the VF CDK  instead of an apex:outputPanel to wrap things (it works because custom components do things correctly and a couple of our standard components that have not been rewritten yet as CDK misbehave in this case).

NOTE: I also simplifed the impementation of getShowTable() but that is not material to the workaround just a stylistic recommendation.

NOTE 2: I also moved the apex:form tag out of the component - again not material to the fix. Be very careful about creating components that embedd apex:form, there is a cost in page size for each and every apex:form used and these can add up quickly (there is a bug to improve this BTW). In general let VF enforce your component's form requirements for you and leave the form out of the component itself.

<apex:page > <apex:form> <c:componentissue /> </apex:form> </apex:page>

<apex:component controller="componentIssue">
<apex:actionRegion>
<apex:selectList value="{!picklistValue}">
<apex:selectOption itemValue="hide" itemLabel="hide"/>
<apex:selectOption itemValue="show" itemLabel="show"/>
<apex:actionSupport event="onchange" rerender="table"/>
</apex:selectList>
</apex:actionRegion>
<c:panel id="table">
{!showTable}
<apex:pageBlock rendered="{!showTable}">
<apex:pageBlockTable value="{!Accts}" var="a">
<apex:column value="{!a.Name}"/>
</apex:pageBlockTable>
</apex:pageBlock>
</c:panel>
</apex:component>

public class componentIssue {
public String picklistValue {get; set;}

public List<Account> getAccts(){
return [select Name from Account limit 10];
}

public Boolean getshowTable(){
return picklistValue == 'show';
}
}

/apexcomponent/panel <apex:component> <apex:componentBody/> </apex:component>