At least the Amazon claim is possible (if trivial)
This cannot be said of patent 5,533,051 on compression of random data, a beautiful discussion of which can be found on:
http://gailly.net/05533051.html
This claims to be able to compress ANY data string by at least one bit without loss of information. This means that recursive application to any file could reduce it to 0 bits without loss. Now certain (particularly repetitive) songs might be compressible to this extent without any loss whatsoever (the complete works of Paris Hilton somehow spring to mind), but I suspect most medics would be less than impressed if anyone did this to their digital X-ray images.
The USPTO has a lot to answer for. At least they are trying to address the problem.