Consider a square grid of size $72 \times 72$. We need to determine if Vova can always cut out a clean $3 \times 3$ square without its central cell, given that some cells are stained.

### Part a) When $n = 699$

1. Calculate Total Cells:
$$72 \times 72 = 5184$$
There are 5184 cells in total.

2. Calculate Clean Cells:
$$\text{Clean cells} = 5184 - 699 = 4485$$

3. **Determine Clean $3 \times 3$ Squares:**
- Each $3 \times 3$ square without the central cell contains 8 cells.
- For Vova to be unable to cut out such a square, all possible arrangements of $3 \times 3$ squares must contain at least 1 stained cell.

4. **Calculate Total $3 \times 3$ Configurations:**
$$(72 - 2) \times (72 - 2) = 70 \times 70 = 4900$$
There are 4900 possible $3 \times 3$ square arrangements.

5. Compare Clean Cells and Required Conditions:
- The number of clean cells (4485) is more than half of the total possible $3 \times 3$ square configurations (2450 if each were to perfectly avoid repeats).
- Since 4485 clean cells is more than half, Vova can always find a $3 \times 3$ configuration with only clean cells (fewer than $4900$ is required due to overlapping).

Thus, for $n = 699$, Vova can always cut out a clean $3 \times 3$ square without its central cell.

### Part b) When $n = 750$

1. Calculate Clean Cells:
$$\text{Clean cells} = 5184 - 750 = 4434$$

2. **Compare with the Requirement for Clean $3 \times 3$ Squares:**
- The reasoning is similar to part (a).
- However, with 4434 clean cells, ensuring a clean $3 \times 3$ square for all 4900 possible positions without overlapping via excess becomes untenable.

From combinatorial reasoning and applications of the pigeonhole principle, it's clear that with 4434 clean cells, intersections among the $3\times3$ blocks will eventually prohibit finding one clean block for every arrangement.

Thus, for $n = 750$, Vova cannot always cut out a clean $3 \times 3$ square without its central cell.

Therefore, the final answers are:
$$\boxed{\text{a) Yes, b) No}}$$