T>Если DataAdapter.Fill(datatable) выполняю в основном потоке, то он его полностью занимает и пока не выполнится, прогресс не идёт.

Дело видимо, в том, что если вы делаете Fill в параллельном потоке, то и события для обновления прибинденных контролов расходятся синхронно в параллельном потоке. Это вообще плохо.

T>В общем что ни пытюсь сделать — натыкаюсь на непреодолимый тупик.
T>Неужели такую простую вещь как Progress bar невозможно сделать?

Попробуйте делать в параллельном потоке Fill в отсоединенный от контролов DataSet, а потом в основном потоке подключать его к гриду или куда там вы его подключаете.