the "MPEG audio header not found." bit makes me think that something is wrong with your MP3 files, you may want to try repairing the headers using a program that does so...
In case you want to use foobar2000, you can do this:
Add the files YAAP can't untag to a playlist, select them all, right click one of them, select Utilities, click "Fix VBR MP3 Header...", answer "Yes", let it finish the process and then try to untag them using YAAP again.
EDIT: In case that doesn't work, repeat the steps, but this time use "Rebuild MP3 Stream..." instead of "Fix VBR MP3 Header...", the procedure is exactly the same.