Yes, OLD_VALUE does not support reference attributes yet. You can use the following workaround for single reference attributes. Add attribute MyDepartmentID to object Employee of type Number and the following rule:
Employee.MyDepartmentID = Employee.MyDepartment.ID
You can access the original reference object like this:
FIND Department WHERE Department.ID = OLD_VALUE(Employee.MyDepartmentID)