I spent some time today gutting my table code until the problem disappeared.  I was able to narrow the problem down to the filterBy attribute on the rich:column.  Once I did this, I created an independent test example in order to demonstrate the problem in isolated code.  For some reason, when the filterBy attribute is present on any of my columns, the keys being used by the table selection are all integers corresponding to the visible location of the selected row on the page.  When I remove filterBy, the keys are all UUIDs corresponding to the actual keys of the entities backing each row (as returned by getKey in the DataProvider implementation).  I'll paste in my test code below.  Note: Column A contains the filterBy which triggers the use of generated Integers rather than the key from the DataProvider:

**** tabletest.html ****

     . . .

        <div style="width: 1024px; height: 500px">
                
             <rich:extendedDataTable id="testtable"
                                     value="#{testTableBB.dataModel}"
                                     selectionMode="multi"
                                     selection="#{testTableBB.selection}"
                                     var="rowRecord">

                <a4j:support event="onselectionchange"
                              action="#{testTableBB.onSelectionChanged}"
                              ajaxSingle="true"
                              limitToList="true"
                              reRender="testtable"/>

                <rich:column id="columnA"

                                                          filterBy="#{rowRecord.name}">
                     <f:facet name="header"><h:outputText value="Name"/></f:facet>
                     #{rowRecord.name}
                 </rich:column>
                
                 <rich:column id="columnB" width="300px">
                     <f:facet name="header"><h:outputText value="ID"/></f:facet>
                     #{rowRecord.id}
                 </rich:column>

           
             </rich:extendedDataTable>
        
         </div>

. . .

***** TestTableBB.java ******

package org.dummy.test;

import java.io.Serializable;
import java.util.Iterator;

import org.jboss.seam.ScopeType;
import org.jboss.seam.annotations.Name;
import org.jboss.seam.annotations.Scope;
import org.richfaces.model.DataProvider;
import org.richfaces.model.ExtendedTableDataModel;
import org.richfaces.model.selection.Selection;

/**
* Seam component backing-bean
*
*/
@Name("testTableBB")
@Scope(ScopeType.CONVERSATION)
@SuppressWarnings("unchecked")
public class TestTableBB implements Serializable {

    /** */
    private static final long serialVersionUID = 1L;

    private Selection selection = null;
   
    private ExtendedTableDataModel dataModel = null;
   
    /**
     *
     * @return data model
     */
    public ExtendedTableDataModel getDataModel() {
        if (dataModel == null) {
            dataModel = new ExtendedTableDataModel(createDataProvider());
        }
        return dataModel;
    }
   
   
    private DataProvider createDataProvider() {
        return new TestTableDataProvider();
    }

    /**
     *
     * @param selection
     */
    public void setSelection(Selection selection) {
        this.selection = selection;
    }
   
    /**
     *
     * @return selection
     */
    public Selection getSelection() {
        return selection;
    }
   
    /**
     *
     */
    public void onSelectionChanged() {
        if (selection != null) {
            System.out.println("Selected keys: ");
            Iterator it = selection.getKeys();
            while (it.hasNext()) {
                Object key = it.next();
                System.out.println("key: "+key);
            }
        } else {
            System.out.println("No selection is set.");
        }
    }
}

/**** TestTableDataProvider.java *****/

package org.dummy.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.UUID;

import org.richfaces.model.DataProvider;

/**
*
*
*/
@SuppressWarnings({"unchecked" })
public class TestTableDataProvider implements DataProvider {

    /** */
    private static final long serialVersionUID = 1L;

    private Map<UUID,TestTableDummyEntity> dataTable;
    private List<TestTableDummyEntity> dataList;

    /**
     *
     */
    public TestTableDataProvider() {
       TestTableDummyEntity entityA = createEntity("Entity A");
       TestTableDummyEntity entityB = createEntity("Entity B");
      
       dataTable = new HashMap<UUID,TestTableDummyEntity>();
       dataTable.put(entityA.getId(), entityA);
       dataTable.put(entityB.getId(), entityB);
      
       dataList = new ArrayList<TestTableDummyEntity>(2);
       dataList.add(entityA);
       dataList.add(entityB);
    }
   
    private TestTableDummyEntity createEntity(String name) {
        TestTableDummyEntity entity = new TestTableDummyEntity();
        entity.setId(UUID.randomUUID());
        entity.setName(name);
        return entity;
    }

    public Object getItemByKey(Object key) {
        UUID id = (UUID)key;
        return dataTable.get(id);
    }

    public List getItemsByRange(int start, int end) {
        return dataList.subList(start, end);
    }

    public Object getKey(Object entity) {
        return ((TestTableDummyEntity)entity).getId();
    }

    public int getRowCount() {
        return dataList.size();
    }

}

**** TestTableDummyEntity.java ****

package org.dummy.test;

import java.util.UUID;

/**
*
*
*/
public class TestTableDummyEntity {

    private UUID id;
    private String name;

    /**
     * @return the id
     */
    public UUID getId() {
        return id;
    }
    /**
     * @param id the id to set
     */
    public void setId(UUID id) {
        this.id = id;
    }
    /**
     * @return the name
     */
    public String getName() {
        return name;
    }
    /**
     * @param name the name to set
     */
    public void setName(String name) {
        this.name = name;
    }
   
   
}