I think I recall that for Debian, cyrus-imapd is split into several separate packages, rather than just one. I guess there's a list somewhere of which tools get put in which package? So I imagine maybe that list needs to be updated to include these tools. I think they should probably be in whichever package contains "reconstruct".
reconstruct is in cyrus-common
dpkg -L cyrus-common | grep reconstruct /usr/lib/cyrus/bin/reconstruct /usr/share/man/man8/cyrus-reconstruct.8.gz
