Effective space utilization is an important consideration in logistics systems and is especially important in dense storage environments. Dense storage systems provide high-space utilization; however, because not all items are immediately accessible, storage and retrieval operations often require shifting of other stored items in order to access the desired item, which results in item location uncertainty when asset tracking is insufficient. Given an initial certainty in item location, we use Markovian principles to quantify the growth of uncertainty as a function of retrieval requests and discover that the steady state probability distribution for any communicating class of storage locations approaches uniform. Using this result, an expected search time model is developed and applied to the systems analyzed. We also develop metrics that quantify and characterize uncertainty in item location to aid in understanding the nature of that uncertainty. By incorporating uncertainty into our logistics model and conducting numerical experiments, we gain valuable insights into the uncertainty problem such as the benefit of multiple item copies in reducing expected search time and the varied response to different retrieval policies in otherwise identical systems.