From what I can tell this is a bug in ext. There is a totalLength property that the pager uses to determine pagesize. This property is only updated in the loadRecords method. So here is workaround to get the pager to clear out:

Code:
store.removeAll();
store.totalLength = 0;
pager.onLoad(
                store,
                null,
                {
                    params: {
                        start: 0
                    }
                }
            );