Problem with pathfinder / colors

Hi all,

I'm currently working on two projects that I'm having problems with.

Both coat of arms are made of scanned drawings for which I used live trace.

After that I changed all the black areas into C:40% M:40% Y:40% K:100% but then changed my mind and changed it to C:0% M:0% Y:0% K:100% instead - or so I thought. Because when I changed the global black color into 100% magenta as a test a small area still remains black. And to make matters worse they're both only semi transparent which becomes clear when I put a colored box behind the illustrations. I've tried using pathfinder to solve the problem but with no luck. I'm at the end of my rope hear and have no idea how to solve this. Any suggestions are most welcome!

I can send you the AI files if you PM me your E-mail address since I'm not allowed to add the photos here.