When a ListBox that has an associated ListSearch Extender is first used, the ListSearch Extender does some one-time initialization.

It delays this work this for very good reasons, as Ted Glaza explains here.

The extender needs to decide whether it can use the very fast binary search when the user types, or whether it must use the slower linear search.  It does this by determining if the list is sorted, which can take a long time if there are thousands and thousands of entries in the ListBox.

The best thing would be to somehow give the ListSearch Extender a hint as to whether the ListBox is already sorted or not.

You can do this by making a couple of changes to the ListSearch extender.  If you'd like to see this behaviour become a standard part of the ListSearch Extender, please vote for it and I'll add it if there is sufficient interest.

Modifying the ListSearch Extender is extremely simple.  First download the AJAX Control Toolkit, and then open the AjaxControlToolkit.sln

Open the behaviour JavaScript file "ListSearchBehavior.js".  At the top of the file you'll see some properties.

Add a couple of new property:
    // Properties
    this._isSortedHintSet = false;
    this._isSortedHint = false;
...

These indicate whether the user has told the extender if the list is sorted or not, and if so, whether it is sorted.

Next find the "_isSorted" function, and at the start of it (after the documentation comment), add this code:

if(this._isSortedHintSet) {
    return this._isSortedHint;
}
...

Finally you need to expose this property so that it can be set from outside the class, although you could actually set the  _isSortedHintSet and _isSortedHint from JavaScript, this is considered very bad form since the underscore prefix indicates they are private.

Define a getter and setter accessor at the end of the bevahior, where you'll find the other accessors:
    get_isSortedHint : function() {
        ///
        /// Where the prompt should be positioned relative to the target control.
        /// Can be Top (default) or Bottom
        ///
        return this._isSortedHint;
    },

    set_isSortedHint : function(value) {
        if (!this._isSortedHintSet || this._isSortedHint != value) {
            this._isSortedHintSet = true;
            this._isSortedHint = value;
            this.raisePropertyChanged('isSortedHint');
        }
    }

If you add these two functions after the existing last function (which is "set_raiseImmediateOnChange" in the current build), then you must be sure to add a comma after the closing brace of this last function:
...
    },

    get_isSortedHint : function() {
....

Build the solution, and make sure projects that use the AJAX Control Toolkit now reference the AjaxControlToolkit.dll in AjaxControlToolkit\AjaxControlToolkit\bin\Debug

Now you can set this property in JavaScript when your page first loads, so that the extender does not have to work out whether the list is sorted: 

    <form id="form1" runat="server">
        <asp:ScriptManager ID="SM1" runat="server" />

        <asp:ListBox ID="LB1" runat="server">
            Hello
        </asp:ListBox>
        <cc1:ListSearchExtender ID="LSE1" runat="server"
            TargetControlID="LB1"></cc1:ListSearchExtender>

        <script language="javascript" type="text/javascript">
            function pageLoad(sender, args) {
                var extender = $find('LSE1');
                if(extender) {
                    extender.set_isSortedHint(true);
                }
            }
        </script>
    </form>

This is the complete code (no changes to the code-behind file).

The pageLoad function is called automatically by the ASP.NET AJAX Framework (see http://ajax.asp.net/docs/overview/AJAXClientEvents.aspx) when all controls within the page have been loaded.

The function first finds the ListSearch Extender, and then gives it a hint that the list that it is targeting is actually sorted.

If you wanted to be able to set the property from the server side, instead of from JavaScript, you can edit the ListSearchExtender.cs file, and add the appropriate declaration of the property: 

        [ExtenderControlProperty]
        [ClientPropertyName("isSortedHint")]
        [DefaultValue("")]
        public string IsSortedHint
        {
            get { return GetPropertyValue("isSortedHint", ""); }
            set { SetPropertyValue("isSortedHint", value); }
        }