With roughly the following layout it is intended users can search for items and select them. Except for some actions where deselection is natural (like Delete), actions preserve selection. Selection is preserved when search criteria are changed, so selection is understood more like "shopping cart": Users can apply whatever filter, manually select desired items, go to other pages, select, etc, until satisfied, after which they apply Action to a selected set. Due to the nature of the application, actions are almost never done on the whole search result set: Manual tuning almost always done by users. Table shows selected items with checked checkboxes (when those happen to be on current result page). As we deal with people, adding direct shopping cart metaphor is not desired.
However, some users are confused and make mistakes working on previous selection to which they add more.
Number of selected items and even confirmations on how many items action will be performed on are displayed clearly. Action buttons disappear when nothing is selected.
It seems like the mental model for this should be quite simple: selection control is explicit, selection persistent.
The question is, what is the problem? Can the current way be improved or should action-on-selection be completely different? Is it purely user interface issue, curable by adding some hints or fundamental usability flaw?
We probably can't redesign the whole thing quickly, so gradual improvement is preferable, but I just can't see any simpler way (wrt users mental model) nearby.
