можно ли написать этот black box так, чтобы гарантировать работоспособность каждого элемента этого black box'а при помощи юнит-тестов? Мой ответ - можно.

Однозначный jein :)

Написать так что тест будет гарантировать работоспособность можно. (но как проверить что написал именно так?) Но этот тест не вскроет ошибки, внесенные пре рефакторинге.

Допустим мы переписали код так, что любой доступ к данным из разных потоков синхронизирован. Ошибок, связанных с параллельным доступом в таком коде не будет, юнит-тест будет находить логические ошибки в коде, все отлично. Через месяц Вася Пупкин делает рефакторинг и добавляет доступ к новому полю данных - не синхронизированный. Обнаружит ли юнит-тест ошибку, связанную с внеочередным доступом к данным? А как повезет.

Чтобы от такого спасаться надо еще и статический анализ кода подключать, да правила ему давать вроде "в классах с аннотацией @ThreadSafe все get/set методы синхронизированы" (конечно, Вася и такое обойти сможет).