In case anyone is interested, I've managed to play around with the Query and find out how to avoid hitting the threshold. What I did was simply change the order of the query elements so that my indexed fields were listed first and the DateRangesOverlap node was listed last. Here is the result that works:
<Where>
<And>
<BeginsWith>
<FieldRef Name="Place" />
<Value Type="Text">Boston</Value>
</BeginsWith>
<And>
<Or>
<Eq>
<FieldRef Name="Status" />
<Value Type="Text">Status1</Value>
</Eq>
<Eq>
<FieldRef Name="Status" />
<Value Type="Text">Status2</Value>
</Eq>
</Or>
<DateRangesOverlap>
<FieldRef Name="EventDate" />
<FieldRef Name="EndDate" />
<FieldRef Name="RecurrenceID" />
<Value Type="DateTime">
<Now />
</Value>
</DateRangesOverlap>
</And>
</And>
</Where>