Think about surveys in the general population of say the US. If we need 50% of the population to determine the majority opinion we would need a sample of about 160 million, which is truly prohibitive. Even a 1% sample is extreme (about 3.2 million), and is rarely done. An important survey in the US the General Social Survey has sample sizes between 1,500 to almost 3,000. So a 25% sample is in itself no problem.
Remember that a survey is not an election or a referendum. For the latter to be legitimate every eligible person must have the opportunity to have their say. For survey the purpose is to get a good estimate of the average opinion, and you can get that with a random sample. So the company needs to decide what the purpose of the survey is: is it a way for employees to give their opinion and participate in the company, or is it a way for the managers to get information?
Both sampling designs ensure that 25% of the employees are asked. The latter ensures that smaller department are represented in the survey. If you care about standard errors then you should take the nested nature of the sampling into account, though I don't suspect that that will matter a great deal in this case.
