Пользовательские заголовки, безусловно, не вариант, даже если некоторые плохо разработанные остальные API используют их.
Параметры запроса обычно предназначены для фильтрации коллекций на основе чего-либо, например, диапазона дат или чего-то подобного, но не грех использовать их для той цели, для которой вы хотите их использовать.
Но, несмотря на все сказанное, я бы использовал субресурсный подход, как вы показали в своем первом примере. Это более понятно, и клиентам не нужно выяснять, как вы называете параметры вашего запроса и сколько их. Вы просто хотите пользователей определенной компании. :)