If it is a truly random selection of the entire employee base, how is that a statistically valid sample assuming all those employees responded?
It is a valid sample as long as it is drawn from the population it is meant to describe. That is, if you only sample bosses, nothing can be said about the other employees; that won't happen in the setting that you have described. It may however happen due to non-response (more on that here below).
If it is random on a per department level e.g. 25% of each department, how is that a valid sample considering one department is over 50% of the total population.
This is no longer a question of sample validity but one of sampling error. Obviously, the most precise estimates would be obtained from a stratified random draw, the stratum encompassing at least the department level. In such a setting, you will have a valid sample for each department but the estimates for small departments will be generally less precise than the estimates for big departments, thanks to the higher absolute sample size for the latter. For the overall organization, the higher sample representation of bigger departments simply reflects the reality of the organization and does in no way reduce the validity of the sample.
The survey is not enforced. There can be no guarantee of a 100% response rate from the 25% selected. There is no incentive or punitive means if the survey is or is not filled out.
You won't be able to force anyone to provide a good answer but implementing a response reminder plan is a minimum. Plus, you should explain the relevance of the survey to the employees (e.g. when are the results published? what are the potential actions undertaken by the organisation based on the survey?), i.e. explain how each single response impacts the organisation and each employees therein.
Once data are collected, non-response is an issue that should be dealt with. Dealing with it means you should first analyse the non-response behaviour to detect any potential patterns: has no boss responded? Has a given department not responded at all? Then adopt the necessary strategy (post-strafification, reweighting, imputation, etc.).