I looked at the FFTs a while ago and found it difficult to consistently identify the overtones (or base frequency) over the background noise. It would be interesting to have a deeper look though - if nothing else I'd like to know how the frequencies change over time (is the increase from segment to segment, or is it linear across the whole recording?) I've got an old matlab script somewhere that I could dig out that could help with this by giving more control over the FFT. I'll try later on if I get chance.
If a sine of a base tone has been subtracted, then I think it it should be possible to identify where it was and add it back in as the base notes will not be clean sines so I think there will be visible artifacts. I suspect this would just change the timbre of the sound - which might fit with the 'shadow' comment.
Forget what I said earlier. Was complete rubbish. Removing a sine wave from the recording of an instrument wouldn't remove the note played on that instrument, because the base note is not a sine wave. If it was, it wouldn't have any overtones and would just be a single line in the spectrum. My failure to predict the resulting spectrum made me think about what the result would look like. So I just tried the procedure. I took a recording of a cello playing a C1 (66Hz), loaded it into audacity and saw parallel lines in the spectrum (as expected at 66Hz, 132Hz, 198Hz, etc.). Then I applied a notch filter at these three frequencies. Result (highlighted part is filtered):

You can listen to it at
http://www.swedorn.net/cello-notch.mp3. So, maybe someone finds such patterns in the recordings of the UA.
I have been wondering if we might be looking at the message structure in the wrong way. Could there be a single message, but we only get to see it in 7-bit segments?
As some purrs fall on the extremes of the envelope and are barely audible, this seems a possibility. If the purrs were all intended to hold information in isolation (a letter or a word for example) I would not expect to see this as it would be important to perceive every bit. To illustrate this, imagine the envelope below which exposing a 7 bit segment from a longer message. With enough segments, it would be possible to reconstruct the original message by identifying points of overlap.
____________/‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾\___________________________________
p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p
So rather than looking for repetition in segments, we should perhaps also be looking for overlapping sequences within the purrs as these could indicate places segments could be joined.
Entirely speculation at the moment, but we should be mindful of all interpretations.
Entirely possible. But why would you assume there will be overlaps in the message parts? Or even worse: some parts of the message ARE garbled (overlapped by other sounds, intentionally, maybe). Still worse: there may be even gaps in the transmission. In such cases the only hope we have is to find common features in the recording to which we could align the parts in order to piece together the message bit by bit.
What I find most interesting is that while whale and tuba sounds do overlap, the chittering is always "clearly" audible, as it always follows the whale sound and seem to never run into the tuba sounds.