A data collection system for, and methods of, providing reliable store-and-forward data handling by encoded information reading terminals can utilize ad-hoc peer-to-peer (i.e., terminal-to-terminal) connections in order to store data that is normally stored on a single terminal only, in a redundant manner on two or more terminals. Each portable encoded information reading terminal can be configured so that when it captures data, a software application causes the terminal to search out nearby peer terminals that can store and/or forward the data to other peer terminals or to a data collection server, resulting in the data having been stored by one or more peer terminals that are immediately or not immediately accessible by the data-originating terminal.