What does iTunes Match think a specific track is

You may not be able to get complete matches, but here's what I have been doing in the cases where one or two tracks don't match.

1. Select the item(s) to attempt to re-match.
2. Right-click on them, and select "Create AAC Version"
3. When this is complete, hit alt-backspace, and choose to remove both the original and the iCloud version. Also choose to delete the items from disk.
4. Go to the "Store" -> "Update iTunes Match" menu item.

Note that this will keep the play counts, etc on your tracks. It may not succeed on every track, and sometimes repeating the process picks up another track.

Occasionally, I'll get a "Removed" icon there after doing this: just right-click and choose "Add to iCloud" on these.

I already answered a related question. I may not know the most definite answer, But I read that iTunes Match uses Gracenote's MusicID program. It seems MusicID uses the following techniques to identify songs.

MusicID-featured Identification Technologies:

CD Identification: Using the CD’s unique Table of Content (TOC), MusicID can identify CDs released around the world. Even with multiple pressings and release dates, patented fuzzy matching enables accurate recognition.

Stream Identification: Using an audio waveform fingerprint technology, MusicID can identify music with short audio samples anywhere in the song.

Digital File Identification: MusicID can identify individual songs or albums in a user’s collection regardless of source, format, or tag information. Utilizing a multi-step process which combines stream identification with textual information analysis from the file’s embedded tags, file name, directory path, and other related files in the user’s collection, individual or groups of songs can be matched to albums.

More here.

To answer your question, they perform some fuzzy text matching algorithm to map meta data and also perform audio waveform analysis.