Given a dataset of employees, their respective companies, and salaries, identify the specific record(s) representing the median salary for each company. In the event of an even number of employees, return both middle records. Ensure the median calculation is deterministic by using the employee ID as a tie-breaker for identical salary values. Your solution should scale efficiently for companies with varying workforce sizes.