The ID of an object is null at start. Does that make the object state invalid and violate encapsulation?

Identify your single source of truth. That's what has the authority.

If your program is the authority on what can and can't happen with an employee then the DB is nothing but a way to persist employee info. The DB id is of no consequence. The object model will have it's own way of identifying and relating entities.

If the DB is the authority on what can and can't happen with an employee then an employee object with no id is simply a pending request to create an employee. An employee object with an id is a stale report of the state of the employee. At no time is the employee object ever the single source of truth about the state of the employee. Anything you wish to change must be checked against the DB.

so if I use the object for describing a new employee, there will be no id to store yet

Then they aren't an employee; they are an applicant. So don't use the Employee type for them. The reason why you are struggling with how to represent this scenario is because you are using the wrong type.

One way is to ensure that new entities do have a valid identifier, before even being saved to a database. This is exactly the benefit of UUID type; you don't need to query the database in order to get a new identifier. Instead, you just create a new UUID, and you know that it is unique, i.e. there are no other entities in the database with the same identifier.

Another way is to avoid creating an instance of the Employee class if you haven't created one yet. In other words, when a user of the application creates an employee, the first step consists of INSERTing a row in the database, and getting back a valid identifier (and other default values, if any). Only then you'll initialize (from the information you just got from the database) an instance of the Employee class.

This second approach has naturally one drawback: you may end up with a lot of unused entities—things that users created inadvertently by opening a form, even if they didn't want to create ones. One way to mitigate this problem is to ensure that the user interface is very clear on the fact that an entity would be created if the user clicks on a button, opens a page, etc. Displaying the list of already created entities should give an immediate feedback. Another approach is to mark an entity as empty if the user haven't saved anything in it. Empty entities could then be deleted on regular basis, such as every night.

A third way, finally, is to have a base class which represents an employee without an identifier. This would, however, make the code more complex than it needs to be, so use this approach only when it brings clear benefits.

I don't know what the answer to your title question is.

But the reality is that all theoretical ideas will be broken when applied to real-world scenarios. And software design is thus job of compromises. Will you break the ideal scenario of "object should always be in correct state" and allow an employee to exist without an Id before it is inserted into database? Or will you create some system that allows you to give Employee an Id on creation? Options are many. Use GUID. Or pre-insert an empty row to get the Id. Or use Hi\Lo algorithm.

In the end, it is up to you, your (hopefully extensive) experience and your specific requirements what option is best.

properly encapsulated object cannot be brought into an invalid state via the public interface...

As mention there, properly encapsulation is the key. Where is your encapsulation for Id ? I really don't get what is for private int Id without encapsulating it.

You can encapsulate it like:

class Employee { private int Id; public int ID { get => Id; set { if (value > 0) { Id = value; } } } // other properties and methods. } 

What's wrong with this Employee class and what makes your Id invalid? This Id can be invalid if you not design your code properly and try to preform CRUD operation when it hasn't valid value.

To achieve this you can determine which method you should run by checking Id. If it is equal to 0 then insert it. If not, then update it. Entity Framework AddorUpdate(TEntity model) extension method is good example for this.