Is callback put on the message queue after 1000ms or is it put to the message queue immediately?

After 1000ms - that's when the timer runs out. If it was put on the message queue immediately, there would be no waiting before is run.

If it is put to the message queue after 1000ms, then does that mean that the 1000 does not mean that the callback will run in 1000, but instead it means that the callback may be run at a minimum only after 1000?

Yes, if the event loop is still busy with other tasks (especially long-running blocking code) at that time, it will have to wait for those to finish. The message queue is a queue, it is serviced one task after the other; no two callbacks are executed in parallel.

(Notice that setTimeout is allowed to lag arbitrarily anyway).

It's really doesn't matter when the callback is added to the queue, because setTimeout is not true async anyway (aka it still runs on the same thread as the rest of the code).

Here is a little example showing how setTimeout is just a suggested minimum wait timeout:

let time = new Date().getTime();
setTimeout(() => test(1), 1000);
setTimeout(() => test(2), 1000);
setTimeout(() => test(3), 1000);
setTimeout(() => test(4), 1000);

function test(id)
{
  console.log(`executed ${id} after `, new Date().getTime() - time);
  for(let i = 0; i < 1000000000; i++)
  {
    i * 9;
  }
}