'cvs rm' can be applied to files already removed from workdir only. However, 'cvs rm -f' can be applied to any file in workdir (and it will be removed). Sadly, bashcomp for 'cvs rm' doesn't support the '-f' switch and therefore autocompletes removed files only. This makes using the bashcomp more painful than beneficial.
This one seems to be fixed upstream. commit 9852597d8c19567ee1e01c03a297692d9c1cd764 Author: Ville Skyttä <ville.skytta@iki.fi> Date: Mon Apr 8 21:53:37 2013 cvs rm: Don't filter existing files with -f (RedHat: #949479). Thanks-to: Hans de Goede <hdegoede@redhat.com>