Dominik found this issue when testing node failover with buddy replication. As commented on the case, testing with the latest build from the JBC 1.4.x branch resolved the issue. This indicates the problem was likely related to http://jira.jboss.com/jira/browse/JBCACHE-1194, which was a data gravitation problem that was causing sessions not to be found on failover.
At this point I hink the key issue here is to try to understand why Dominik was seeing the problem even before he shut down any nodes. The JBCACHE-1194 issue is only an issue when a client fails over; before shutdown there shouldn't have been failovers. Perhaps there is a problem with SFSB server affinity?