rpm сообщает об отсутствии зависимости, но она присутствует?

Используйте опцию -path для этого случая:

find / -type d  -path '*/aaa/bbb'

Из man-страницы для find:

Имя файла соответствует шаблону оболочки. Метасимволы не обрабатывают / или . специально; так, например,

find . -path "./sr*sc"

выведет запись для каталога `./src/misc' (если он существует).

Кросс-платформенная совместимость

Edit: Я только что заметил теги aix и hp-ux.

Вы не указали, какую версию find вы используете, и приведенная выше информация относится к GNU find. Однако, на странице man также указано, что,

предикат -path также поддерживается HP-UX find и будет в ближайшей версии стандарта POSIX.

так что, похоже, -path можно использовать в HP-UX, но не в AIX (по крайней мере, не в AIX 7.1, последнем выпуске по состоянию на 2015-08-24).