[Anton04]

Если менял что-то в GPO на сервере, то когда эти изменения появятся на рабочих станциях: сразу, через вышеуказанные 90 минут или сначала действие какое-то нужно выполнить? »

Сразу ничего никогда нигде не появляется.
Как только истечёт время заданное в GPO, так и обратится ПК пользователя за обновлением политик и для пользователя тоже.

Допустим часть рабочих станций соединяются с контроллером домена через openvpn-соединение, которое в силу своих особенностей поднимается не сразу при загрузке компьютера. Что в данных условиях можно сделать, чтобы политики "Конфигурация пользователя" выполнялись всегда?»

Прописать в GPO ждать загрузки сети.
А далее играться с вашими соединениями и делать так, чтоб они стартовали как службы.
И всё ровно они не будут выполнятся "всегда", т.к. в какой-то промежуток времени контроллер домена будет недоступен, не важно по какой причине.

У меня программы не устанавливаются. »

Печально.... я знаю 7 способов установить ПО посредством GPO штатными средствами, какой используете вы не представляю, а какая у Вас конфигурация сети тем более не имею понятия.