Leider irrt die Manpage.
Sie ist wohl eher schlicht unvollständig - denn als POSIX Regular Expression hat dein Ausdruck eine ganz andere Bedeutung als du vielleicht denkst, da fehlt ein Punkt.
Ich glaube eher, apt-get nutzt zuerst einen eigenen Matching Algorithmus der in der Manpage nicht (mehr?) dokumentiert wird und fällt erst dann auf die POSIX Regular Expressions zurück, wenn er damit nichts gefunden hat. apt-get's eigener Algorithmus scheint dabei, wie du das anschaulich dargestellt hast, für * keine leere Menge zu akzeptieren, was gegen so ziemlich jede gängige Konvention verstößt. In den neueren Manpages steht übrigens auch drin, dass der Fallback auf POSIX Regular Expressions bald entfernt wird, stattdessen soll man apt-patterns benutzen - das würde dann wohl auf ~nnvidia.*
hinauslaufen (oder so ähnlich, wie die RegExp angewendet werden wird in der dazugehörigen Manpage auch nicht beschrieben...)