Some technical info:

The External Media ID (ExtMID) is usually written on an external label which is attached to the outside of the media cartridge. It is used to identify the media before it is inserted into the drive, but is not recorded internally on the media itself.

The Recorded Media ID (RecMID) is an internal label recorded at the beginning of the media. This should be the same as the media ID that is recorded in the volume database. If they do not match when the media gets mounted into the drive and the RecMID is read, the bptm process will freeze the media.

(In answer to Q2. You could end up with frozen media. You need to fix the mismatch. I would freeze the tape anyway and await expiration. Then properly label the tape using bplabel command or the GUI under Media Management branch)

A media with a RecMID is called a labeled volume. Unlabeled volumes do not have a RecMID. When a request for an unlabeled volume takes place, without specifying the RecMID, the ExtMID is referenced by default (even if the ExtMID is not actually recorded on the volume). This is because the system assumes the RecMID and ExtMID labels are the same unless otherwise specified.

(Q3. Issue command vmquery -W -a | awk {print $1, $4) to check for unlabelled tapes.
The first column is the RecMID which is the Media ID written in the volume database.)

References to look at:
http://seer.entsupport.symantec.com/docs/311622.htm
http://seer.entsupport.symantec.com/docs/275000.htm
http://seer.entsupport.symantec.com/docs/245195.htm

in addition to Stuart's comments:
I've seen this happening when there's device mapping mismatch.
At some point in time, multiple jobs were kicked off at the same time. New tapes, K00358 and  K00457 were requested and mounted in 2 different drives. Because the device mapping was wrong, the internal labels got mixed up. 
Restores will be difficult, if not impossible.
You need to 1st of all verify device mapping, then fix internal labels.
If there are images on these tapes, you will need to perform a manual mount. NBU avrd will only recognize the internal label. Duplicate the images that belong to internal label to a different volume pool. Then expire all images belonging to this media id.
 Unfreeze media if frozen, then re-label (use media GUI). De-select the tick-box to verify internal label.

What Marianne has said happened to us following installation of a replacement tape library.

We did not pay enough attention to the config of the 4 drives. When we subsequently labelled all the new tapes, they were loaded ok in all 4 drives, but at least 2 were mapped incorrectly & therefore recorded media & external media ids did not match. This caused no end of issues for the next few days until the config was corrected & the tapes re-labelled!!

If you do re-label the tapes, ensure the tick-box is deselected for label verification as stated by Marianne. If not either the labelling job fails or apparently "succeeds" but does not actually re-label!