Can you suggest some tips for reverse-engineering an image compression method?

Can you suggest some tips for reverse-engineering an image compression
method?

I realize that this isn't a specific programming question as SO likes to
see, but I think that the nature of this problem might yield some really
interesting answers.
I'm reverse-engineering a remote-control protocol for a handheld device.
The device has a 240x320 color touch-screen (looks like an old Palm Pilot,
actually). There is some remote control software which lets a user
interact with the device in a "remote-desktop" style, meaning that the
device sends (over an RS232 line) an image of what's on the screen, and
then the remote control software sends the X,Y coords of a "touch". (this
much has been confided to me by one of the engineers of the device, but he
stopped short of defining the structure of the actual messages).
I've figured out the format of the "touch" message, but the message
containing the screen image eludes me. I'm fairly certain that it's
compressed because the screen messages are about 4kB-8kB in size, and a
240x320 image (even if only using 4 bits per pixel) is at least 38kB.
Also, screen images which have lots of white background, for example,
don't yield message data with lots of repeating values.
I also suspect that it's lossless, as the screen images are pages of icons
(like the home screen on an iPhone, say); stark color changes, hard
edges... not something which lends itself to lossy compression.
I've scanned the beginning of the data for GIF and PNG preambles, to no
avail. But the engineer could have just omitted it, since he/she would
know what format to expect.
It would be nice to get some strategies and tips for gaining insight into
what the nature of the compression is. I realize that this might be a
fool's errand, as compression's whole mission in life, in a sense, is to
eliminate patterns. But I understand that some image compression methods
(especially ones which might be using indexed color) could leave some
tell-tale things somewhere in the compressed output.
So, what I'm looking for, from the community, are answers like:
"If they're using method XYZ, then there will be a dictionary of n bytes
at the beginning which will have these characteristics..."
"The most common image-compression for use in devices like that is ABC,
because there's no patent on it, there are libraries for it in every
language, on every platform, and Motorola makes a chip that does it for
$2"
"There's a image-processing library called libfoo which lets you tell it
to ignore the preamble (which seems to be absent in your messages) and
force it to try to treat the data as any of a dozen image formats. Just
brute-force it and set it loose on offset 0 of the message data, and then
offset 1, etc. until the decoder function returns success for one of the
offsets and formats".
And... any other code-breaking "seeing clues in the noise" guidelines you
might want to share.