Usando in order com uma nova linha como delimitador de parágrafo, podemos fazer:
awk -v RS='in order\n' '/not/{print $0 "in order"}'
awk trata o texto separado pelo padrão em RS (separador de registro) como registros e cada operação é feita em um registro. Portanto, /not/ testa se o registro corresponde a not e, em seguida, imprimimos o registro ( $0 ) juntamente com o texto separador, que foi removido por awk.
Então:
$ mawk -v RS='in order\n' '/not/{print $0 "in order"}' foo
number of characters a[1]
reg1
reg2
reg3
info a[1] is not in order
number of characters a[2]
reg1
reg2
reg3
info a[2] is not in order