I'd say "you're doing it wrong" ;)
Every time you're hitting a limit like that you should stop and ask if that's really what you need to do. Even if you'd be able to input 50K contacts here - what would usability of such monster be? How is user expected to scroll through this? I'd say a lookup with a search function is really the way to go, that's what it is for.
Have you considered using an autocomplete? Jeff Douglas's blog contains a really nice example on dynamic search - it's not exactly autocompletion but you shouldn't have too much trouble modifying it.
An alternative might be @BobBuzzard's VF lookup
Or simply marry jqueryUI autocomplete and a @RemoteAction
But if you insist on reading further... ;)
public class picklistTest{
public String selectedVal {get;set;}
public List<SelectOption> getOptions1(){
List<SelectOption> retVal = new List<SelectOption>();
for(Integer i = 0; i < 1000; ++i){
retVal.add(new SelectOption(String.valueOf(i+1), String.valueOf(i+1)));
}
return retVal;
}
public List<SelectOption> getOptions2(){
List<SelectOption> retVal = new List<SelectOption>();
for(Account a : [SELECT Id, Name FROM Account]){
retVal.add(new SelectOption(a.Id, a.Name));
}
return retVal;
}
public List<SelectOption> getOptions3(){
List<SelectOption> retVal = new List<SelectOption>();
for(Contact c : [SELECT Id, LastName FROM Contact]){
retVal.add(new SelectOption(c.Id, c.LastName));
}
return retVal;
}
}
<apex:page controller="picklistTest">
<apex:form>
<apex:selectList value="{!selectedVal}" size="1">
<apex:selectOptions value="{!options1}"/>
<apex:selectOption itemValue="Hi StackExchange" itemLabel="Hi StackExchange"/>
<apex:selectOptions value="{!options2}"/>
<apex:selectOptions value="{!options3}"/>
</apex:selectList>
</apex:form>
</apex:page>

So you can get your query results, build a <List<List<SelectOption>> for example and then have a combo of <apex:repeat> + <apex:selectOptions>... I still advise against doing this though ;)