You are correct that it is due to Running Status. If you are at a point in the MIDI file where you are expecting a status byte (hex 80 to FF), but you get a data byte instead (hex 00 to 7F), then the previous status byte applies. However, be aware that only status bytes that contain a channel (status bytes hex 80 to EF) are eligible for Running Status. The other three possible "status" bytes in a MIDI file (hex F0, F7, or FF) must always appear, and then the next status byte after that has to appear because Running Status was ended.
As you mentioned, there are two ways to specify the end of a note. A Note On with Velocity 0 indicates the end of a note. A Note Off also indicates the end of a note and lets you specify a "Note Off velocity". Either way is valid.
When you use both Running Status and Note On with Velocity 0 to indicate the end of a note, then you can use one status byte to start a run of notes for a channel.
Let me warn you against simply scanning a MIDI file for a particular hex value. That might happen to work sometimes, but it could catch unwanted matches! For example, hex 99 might appear in a Tempo meta event, or might appear as part of a size value in a track header, or might appear as a delta time value. And as you found out, when Running Status is used, you can't find the events that used Running Status with just a simple scan for the status byte. In order to work reliably, you will have to parse every byte of the MIDI file to tell for certain where every event actually starts.
In the following example, I explained the bytes for the beginning of the DRUMS track in the file 1999.midi. I indicated the use of Running Status with ditto marks (" " " " ). Remember, for reliability, you always have to start parsing from the beginning of the MIDI file, so think of this example as showing a parsing that was already in progress, continuing at the beginning of DRUMS track header.
4D 54 72 6B (start of track header: "MTrk")
00 00 27 7C (track size: 10108 bytes)
00, FF 21 01 00 (+0 ticks, MIDI Port 1)
00, FF 03 05 44 52 55 4D 53 (+0 ticks, Track Name "DRUMS")
00, C9, 00 ( +0 ticks, Program Change Channel 10, Program 1)
00, B9, 07 78 ( +0 ticks, Control Change Channel 10, Controller 7 Volume Value 120)
00, B9, 0A 40 ( +0 ticks, Control Change Channel 10, Controller 10 Pan Value 64)
00, B9, 79 00 ( +0 ticks, Control Change Channel 10, Controller 121 Reset All Controllers Value 0)
00, 5D 00 ( +0 ticks, " " " " Controller 93 Chorus Value 0)
00, 5B 28 ( +0 ticks, " " " " Controller 91 Reverb Value 40)
00, 99, 24 64 ( +0 ticks, Note On Channel 10, Key 36 Velocity 100)
01, 2A 63 ( +1 tick , " " " " Key 42 Velocity 99)
1D, 24 00 (+29 ticks, " " " " Key 36 Velocity 0)
01, 2A 00 ( +1 tick , " " " " Key 42 Velocity 0)
5A, 2A 43 (+90 ticks, " " " " Key 42 Velocity 67)
1E, 2A 00 (+30 ticks, " " " " Key 42 Velocity 0)
5A, 2A 5F (+90 ticks, " " " " Key 42 Velocity 95)
Note that Running Status is usually used to save space, but using it is optional. In this example, some of the Control Changes could have used Running Status to skip the status byte, but they didn't for some reason. This is valid.
Be sure to read up about delta times and variable length quantities. In this example, the events are close together and the delta times all happen to be one byte. But delta times use a special encoding pattern the spec calls a "variable length quantity" that can be one to four bytes long.
If you have read about MIDI files on other websites, be sure to also check out the official specification on midi.org for comparison (login required to download):
Other websites can describe the specs in a more friendly way, but they might get some details wrong, so it's good to compare with the official specs.