OK, so I really don't get the point why mountall (and cryptsetup) depends on plymouth now. Until this will be resolved (hah!) and with me being stubborn enough not to install plymouth again (after forcefully removing it), I'm left with:

# apt-get install foo
Reading package lists... Done
Building dependency tree
Reading state information... Done
You might want to run `apt-get -f install' to correct these:
The following packages have unmet dependencies:
  cryptsetup: Depends: plymouth but it is not going to be installed
  mountall: Depends: plymouth but it is not going to be installed
E: Unmet dependencies. Try 'apt-get -f install' with no packages (or specify a solution).

Not a nice thing to be stuck with. But equivs is here to help:

$ equivs-control plymouth-dummy
$ vi plymouth-dummy
[...]

$ grep -v ^\# plymouth-dummy
Section: misc
Priority: optional
Standards-Version: 3.6.2

Package: plymouth-dummy
Provides: plymouth
Description: plymouth-dummy, see LP# 556372

$ equivs-build plymouth-dummy 
$ ls -lgo plymouth-dummy*
-rw-r----- 1  826 2010-04-08 16:45 plymouth-dummy
-rw-r--r-- 1 2040 2010-04-08 16:47 plymouth-dummy_1.0_all.deb

Then I was able to install plymouth-dummy_1.0_all.deb (via dpkg -i) onto the system in question. Mind you, the equivs thing was done on a Debian/powerpc system, as I couldn't even "apt-get install equivs" on this b0rken Ubuntu/amd64 box. Talk about portability! :-)