It's because of the log chain, mirroring is kind of like restoring transaction log backups to the other server but automatically, for it to work, you need an unbroken log chain from a full backup to the last t-log backup, so the log chain will look like this (with nice sequential LSNs):
Full-1->LogA->LogB->LogC->Full-2->LogD->LogE->LogF etc...
So in the example above, if you restored the Full-1 backup, you can restore log backups A,B,C but not D,E,F. You can only restore those if you restore Full-2.
In mirroring, you take a Full backup of the DB and then restore it, SQL server then looks at the Log Sequence Numbers (LSNs) and transfers transactions that aren't present in the restored mirror database, if you take another full backup, you break the chain of sequential LSNs.
In your case, it's like you restored Full-1 and then tried to apply Logs D,E,F to it, there is a gap in the sequence numbers. It should have worked for you if you had just re-restored the second accidental backup that you took to the mirror server and then started mirroring. By changing the recovery model, you completely reset the log chain and have to start again.