Los ejecutables de 32 y 64 bits (.exe, .dll, .sys, etc) de los OS's modernos, comenzarán com "MZ" ya que son archivos PE ó PE+ (https://en.wikipedia.org/wiki/Portable_Executable)

Ahora, existen aún los ejecutables de 16 bits, los cuales son NE (https://en.wikipedia.org/wiki/New_Executable)

Cabe destacar que también están los LE (Linear Executables: http://fileformats.archiveteam.org/wiki/Linear_Executable) pero estos también comienzan con "MZ".

Ojo, para determinar si es un ejecutable, deberías colocar más checks aparte de que comience con "MZ" solamente. Por ej., podrías buscar el "PE" que está en el offset marcado por el campo e_Ifanew del MSDOS HEADER.

Saludos!

EDIT: Lo anterior es para Windows.