Depois de muito quebrar a cabeça, cheguei na seguinte solução:
([A-Za-z ]+)|(\|\d{2,3}?\|)|(\d{5}[-.]?\d{3})\
Onde ([A-Za-z ]+) retorna os nomes e as ruas, (\|\d{2,3}?\|), retorna os números das casas, e (\d{5}[-.]?\d{3}) retorna os CEPs. Os pipes | separam cada RegEx para que funcionem individualmente.
