Why would installed packages have status "Remove"?

Solution 1:

_{disclaimer: i'm not a pro when it comes to distributions, so these are just my guesses by putting 1 and 1 multiple times together.}

prologue

on an older Ubuntu machine i have one package with status ri, which is libllvm5.0 (and a bunch of other normal ii-packages like libllvm4.0 and libllvm6.0). the packages <= libllvm5.0 are marked as manually installed but libllvm6.0 is marked as automatically installed.
so my guess would be, that it was a dependency and got obsolete ether by upgrading or removing the dependent package.

explanation

going through your arguments/conditions one by one:

• i only use --no-install-recommends:
  well, needed dependencies are installed nevertheless, else the program wouldn't work.
• autoremove does nothing to these packages:
  well, kind of... i'm pretty sure all the ri-packages left alone by autoremove are marked as manually installed, although you have never installed it "separately". this is because after an initial setup a very few (if any?) packages are marked as automatically installed due to the fact that it isn't really possible to determine what packages you would have installed intentionally because this would vary from user to user. (so... a kind of "you have manually installed your OS".)
• could sudo apt dist-upgrade cause this?:
  no and yes... sudo apt dist-upgrade on itself does not cause this, but with upgrading the whole system it is much more likely, that a bunch of (initially installed) packages will get obsolete.

to wrap up THE REASON: my guess would be that that these packages were installed by the initial setup, therefore marked as manually installed and then got obsolete by upgrading some packages or the whole distribution. and because they are marked as manually installed, they aren't touched by autoremove.