Re-encoding at the same bit rate won't work, in fact it may make things worse as transcoding (that is what re-encoding at different bitrates is called) is going to change the nature of the compression, you are recompressing an already compressed file is going to lead to a significantly different file.
This is a little out of my league but I would approach the problem by looking at the wave pattern of the MP3. Either by converting the MP3 to an uncompressd .wav or maybe by just running the analysis on the MP3 file itself. There should be a library out there for this. Just a word of warning, this is an expensive operation.
Another idea, use ReplayGain to scan the files. If they are the same song, they should be be tagged with the same gain. This will only work on the exact same song from the exact same album. I know of several cases were reissues are remastered at a higher volume, thus changing the replaygain.
EDIT:
You might want to check out http://www.speech.kth.se/snack/, which apparently can do spectrogram visualization. I imagine any library that can visual spectrogram can help you compare them.
This link from the official python page may also be helpful.