This is Thread-Safe right?

Question 1

No, if (_count >= MAXIMUM) return; is not thread safe.

edit: You'd have to lock around the read too, which should then logically be grouped with the increment, so I'd rewrite like

private int _count;

private readonly Object _locker_ = new Object();

public void CheckForWork() {
    lock(_locker_)
    {
        if (_count >= MAXIMUM)
            return;
        _count++;
    }
    Task.Run(() => Work());
}

public void CompletedWorkHandler() {
    lock(_locker_)
    {
        _count--;
    }
    ...
}

Question 2

This is thread safe, right?

Suppose MAXIMUM is one, count is zero, and five threads call CheckForWork.

All five threads could verify that count is less than MAXIMUM. The counter would then be bumped up to five and five jobs would start.

That seems contrary to the intention of the code.

Moreover: the field is not volatile. So what mechanism guarantees that any thread will read an up-to-date value on the no-memory-barrier path? Nothing guarantees that! You only make a memory barrier if the condition is false.

More generally: you are making a false economy here. By going with a low-lock solution you are saving the dozen nanoseconds that the uncontended lock would take. Just take the lock. You can afford the extra dozen nanoseconds.

And even more generally: do not write low-lock code unless you are an expert on processor architectures and know all optimizations that a CPU is permitted to perform on low-lock paths. You are not such an expert. I am not either. That's why I don't write low-lock code.

Question 3

That's what Semaphore and SemaphoreSlim are for:

private readonly SemaphoreSlim WorkSem = new SemaphoreSlim(Maximum);

public void CheckForWork() {
    if (!WorkSem.Wait(0)) return;
    Task.Run(() => Work());
}

public void CompletedWorkHandler() {
    WorkSem.Release();
    ...
}

Question 4

No, what you have is not safe. The check to see if _count >= MAXIMUM could race with the call to Interlocked.Increment from another thread. This is actually really hard to solve using low-lock techniques. To get this to work properly you need to make a series of several operations appear atomic without using a lock. That is the hard part. The series of operations in question here are:

Read _count
Test _count >= MAXIMUM
Make a decision based on the above.
Increment _count depending on the decision made.

If you do not make all 4 of these steps appear atomic then there will be a race condition. The standard pattern for performing a complex operation without taking a lock is as follows.

public static T InterlockedOperation<T>(ref T location)
{
  T initial, computed;
  do
  {
    initial = location;
    computed = op(initial); // where op() represents the operation
  } 
  while (Interlocked.CompareExchange(ref location, computed, initial) != initial);
  return computed;
}

Notice what is happening. The operation is repeatedly performed until the ICX operation determines that the initial value has not changed between the time it was first read and the time the attempt was made to change it. This is the standard pattern and the magic all happens because of the CompareExchange (ICX) call. Note, however, that this does not take into account the ABA problem.¹

What you could do:

So taking the above pattern and incorporating it into your code would result in this.

public void CheckForWork() 
{
    int initial, computed;
    do
    {
      initial = _count;
      computed = initial < MAXIMUM ? initial + 1 : initial;
    }
    while (Interlocked.CompareExchange(ref _count, computed, initial) != initial);
    if (replacement > initial)
    {
      Task.Run(() => Work());
    }
}

Personally, I would punt on the low-lock strategy entirely. There are several problems with what I presented above.

This might actually run slower than taking a hard lock. The reasons are difficult to explain and outside the scope of my answer.
Any deviation from what is above will likely cause the code to fail. Yes, it really is that brittle.
It is hard to understand. I mean look at it. It is ugly.

What you should do:

Going with the hard lock route your code might look like this.

private object _lock = new object();
private int _count;

public void CheckForWork() 
{
  lock (_lock)
  {
    if (_count >= MAXIMUM) return;
    _count++;
  }
  Task.Run(() => Work());
}

public void CompletedWorkHandler() 
{
  lock (_lock)
  {
    _count--;
  }
}

Notice that this is much simpler and considerably less error prone. You may actually find that this approach (hard lock) is actually faster than what I showed above (low lock). Again, the reason is tricky and there are techniques that can be used to speed things up, but it outside the scope of this answer.

¹The ABA problem is not really an issue in this case because the logic does not depend on _count remaining unchanged. It only matters that its value is the same at two points in time regardless of what happened in between. In other words the problem can be reduced to one in which it seemed like the value did not change even though in reality it may have.

Question 5

Define thread safe.

If you want to ensure that _count will never be greater than MAXIMUM, than you did not succeed.

What you should do is lock around that too:

private int _count;
private object locker = new object();

public void CheckForWork() 
{
    lock(locker)
    {
        if (_count >= MAXIMUM) return;
        _count++;
    }
    Task.Run(() => Work());
}

public void CompletedWorkHandler() 
{
    lock(locker)
    {
        _count--;
    }
    ...
}

You might also want to take a look at The SemaphoreSlim class.

Question 6

you can do the following if you don't want to lock or move to a semaphore:

if (_count >= MAXIMUM) return; // not necessary but handy as early return
if(Interlocked.Increment(ref _count)>=MAXIMUM+1)
{
    Interlocked.Decrement(ref _count);//restore old value
    return;
}
Task.Run(() => Work());

Increment returns the incremented value on which you can double check whether _count was less than maximum, if the test fails then I restore the old value