Visual search is a core component of mixed reality (MR) interactions, influenced by the complexities of MR application contexts. In this paper, we investigate how prevalent factors in MR influence visual search performance and spatial regularity memory -- including the physical environment complexity, secondary task presence, virtual content depth and spatial layout configurations. Contrary to prior work, we found that the secondary auditory task did not have a significant main effect on visual search performance, while significantly elevating higher perceived workload measures in all conditions. Complex environments and varied virtual elements depths significantly hinder visual search, but did not significantly increase perceived workload measures. Finally, participants did not explicitly recognize repeated spatial configurations of virtual elements, but performed significantly better when searching repeated spatial configurations, suggesting implicit memory of spatial regularities. Our work presents novel insights on visual search and highlights key considerations when designing MR for different application contexts.