awk
Com o GNU awk ou mawk você poderia fazer assim:
awk -v RS='!\n' '!/shutdown/'
Saída:
interface FastEthernet0/1
ip address 10.16.0.1 255.255.255.224
Você poderia tornar a correspondência mais precisa se procurar apenas o desligamento na terceira linha:
awk -v RS='!\n' -v FS='\n +' '$3 !~ /shutdown/'
sed
Você também pode usar sed, mas é mais complicado.
Uma abordagem é aquela com a qual você começou, mas colete todo o registro em espaço antes de imprimir qualquer coisa. Isso funciona com o GNU sed:
sed -n '/^interface/,/^!/ H; 1b; /^!/ { z; x; s/^\n//g; /shutdown/!p }'