I am just posting this in case it helps anyone else.

I was getting a "Requested record cannot be found by key" exception from the WebDataGrid after binding a new datasource.  My scenario was that I had an autopostback radiobutton list and when the server side event handler was called, I called a database query (that returned a dataset) depending on which radiobutton was selected.  All the queries returned the same schema, merely the where clause was different.

The used could select one radio button and it would postback and the database would be queried and the results populated into the WebDataGrid.  Select another radio button and a different query would execute and its results would populate the WebDataGrid.  The exception would occur if you made a change to a field in the WebDataGrid and then selected a different radio button.  Apparently this is caused by some race condition in the events.  My radiobutton's autopostback SelecedtIndexChanged event was getting fired before the WebDataGrid had the opportunity to update its DataSource with any changes from the posted back WebDataGrid.

So, the SelecedtIndexChanged event was getting called and I was changing the grid's DataSource.  Then the grid tried to update the datasource on the row that had been changed but that row didn't exist any more because I just bound a different data source and this causes the "Requested record cannot be found by key" exception.

My solution was to stop the radio button from autoposting back and unmapping the SelectedIndexChanged event and instead add a hidden button that would have its client side onclick event mapped to a javascript function that would obtain a reference to the hidden button and call its click event.  Then on the server side, make the button's click event do whatever the SelectedIndexChanged event did.  Here are the steps one by one that I took:

1.  Add a button to the page and map its (server) Click event to a server handler method.

 <asp:Button ID="RadioButtonAutoPostbackProxy" runat="server" Text="RadioButton AutoPostback Proxy" onclick="RadioButtonAutoPostbackProxy_Click" />

2.  Add code to the button's server click handler method that does the same processing that would be done by the radiobuttonlist's SelectedIndexChanged event handler.

3.  Remove the mapping of the radiobuttonlist's SelectedIndexChanged event handler (and delete the server side method if this solutions works).

4.  Change the radiobuttonlist so that it is no longer autopostback.

 <asp:RadioButtonList ID="SearchTypeRadioButtonList" runat="server" CssClass="LabelText HorizontalRadioButton" RepeatDirection="Horizontal" AutoPostBack="false">

Now is a good time to test to see if this approach will resolve your exception.

Load the page. Select a radiobutton and click the newly added button.  The grid should populate. Select a different radiobutton and click the newly added button and the grid should populate. Change one of the grid records' data values. Select a different radiobutton and click the newly added button.  If the grid populates and you don't get an exception, this solution will work for you.  If not, look for a different solution.

Assuming the test above worked...

6.  Make the newly added button hidden on the page by setting its style attribute's display property to none.

<asp:Button ID="RadioButtonAutoPostbackProxy" runat="server" Text="RadioButton AutoPostback Proxy" onclick="RadioButtonAutoPostbackProxy_Click" style="display: none;" />

7.  Map a client side onclick event to each radio button that when called, obtains a reference to the newly added button and calls its click() method.  I am using jquery in my code below but if you don't have jquery, just use js.

<script type="text/javascript">
    function pageLoad(sender, args) {
         $(':radio[name="<%= RadioButtonList1.UniqueID %>"]').click(function () {
              $('#<%= RadioButtonAutoPostbackProxy.ClientID %>').click();
         });
    }
 </script>

So now, when a user clicks a radio button, instead of the radio button automatically posting back and calling its SelectedIndexChanged handler, a client side click event handler is called that gets a reference to the button and calls its click() method.  This causes the button to go through its normal click processing which apparently occurs after the grid has attempted to update its DataSource with changes in the grid.