I get the following:

zira:~> apt-show-versions -a libreoffice-common
libreoffice-common:all 4:7.5.4-4 install ok installed
libreoffice-common:all 4:7.4.5-3     stable       ftp.debian.org
No stable-updates version
libreoffice-common:all 4:7.4.7-1     testing      ftp.debian.org
No unstable version
libreoffice-common:all 4:7.5.5~rc1-2 experimental ftp.debian.org
libreoffice-common:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2

The "libreoffice-common:all/experimental *manually* upgradeable"
is wrong, because the installed version was the unstable version
(not an experimental version), and for some reason, it has been
removed from unstable.

Ditto for the other "Architecture: all" packages from the
libreoffice source:

zira:~> apt-show-versions -u | grep manually
fonts-opensymbol:all/experimental *manually* upgradeable from 4:102.12+LibO7.5.4-4 to 4:102.12+LibO7.5.5~rc1-2
liblibreoffice-java:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-common:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-java-common:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-nlpsolver:all/experimental *manually* upgradeable from 4:0.9+LibO7.5.4-4 to 4:0.9+LibO7.5.5~rc1-2
libreoffice-report-builder:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-script-provider-bsh:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-script-provider-js:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-script-provider-python:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-style-colibre:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2
libreoffice-wiki-publisher:all/experimental *manually* upgradeable from 4:1.2.0+LibO7.5.4-4 to 4:1.2.0+LibO7.5.5~rc1-2
libunoloader-java:all/experimental *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2

This is actually the *first* issue I had at
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=858337#5

Now I can give more information:

zira:~> grep '^Package: libreoffice-common' /var/lib/apt/lists/*Packages
/var/lib/apt/lists/ftp.debian.org_debian_dists_experimental_main_binary-amd64_Packages:Package: libreoffice-common
/var/lib/apt/lists/ftp.debian.org_debian_dists_stable_main_binary-amd64_Packages:Package: libreoffice-common
/var/lib/apt/lists/ftp.debian.org_debian_dists_testing_main_binary-amd64_Packages:Package: libreoffice-common

but

zira:~> grep '^Package: libreoffice$' /var/lib/apt/lists/*Packages
/var/lib/apt/lists/ftp.debian.org_debian_dists_experimental_main_binary-amd64_Packages:Package: libreoffice
/var/lib/apt/lists/ftp.debian.org_debian_dists_stable_main_binary-amd64_Packages:Package: libreoffice
/var/lib/apt/lists/ftp.debian.org_debian_dists_testing_main_binary-amd64_Packages:Package: libreoffice
/var/lib/apt/lists/ftp.debian.org_debian_dists_unstable_main_binary-amd64_Packages:Package: libreoffice

I suspect that the amd64 packages could be uploaded but there was some
failure with the "Architecture: all" packages, with the additional
consequence that the old unstable version is no longer listed.

As you can see, this is not the first time this occurs, and
apt-show-versions should handle that to avoid outputting incorrect
information. Perhaps some special detection concerning unstable vs
experimental in case of "No unstable version".

[...]

Note that this is a completely different bug than the one fixed
in 0.22.14. For the one fixed in 0.22.14, the cache was incorrect
(and one of the first lines of the output was incorrect too as a
consequence).

Here, on the contrary, the cache is correct, and the output is
correct except the last line.

A first thing to do could be to stop writing "/experimental" if
it can't be sure (ditto for the other distributions). At least the
line would no longer be misleading. This may even be sufficient.

Or perhaps write something like

  libreoffice-common:all *manually* upgradeable from 4:7.5.4-4 to 4:7.5.5~rc1-2 (experimental)

or it could give more information, such as

  libreoffice-common:all *manually* upgradeable from 4:7.5.4-4 (> unstable) to 4:7.5.5~rc1-2 (experimental)

or

  libreoffice-common:all *manually* upgradeable from 4:7.5.4-4 (unknown) to 4:7.5.5~rc1-2 (experimental)

depending on whether there is an unstable version (first case)
or not (second case).