cdparanoia-3.9.8-r2 and cdparanoia-3.9.8-r3 install some of their files into /--prefix/ when using et_EE locales. Using sys-devel/flex/files/flex-configure-LANG.patch seems to solve this problem for both ebuilds.
Fixed, thanks.