The minimum of $N$ is 201.

In an arbitrary configuration take the minimal rectangle $R$ that contains all black cells. Choose a black cell on every side (there is at least one by minimality) and label these $A, B, C, D$ as in the first figure. Consider the special rectangles $[AB], [BC], [CD], [DA]$ and $[AC]$. Here we write $[XY]$ for the grid rectangle with opposite corner cells $X$ and $Y$ (they determine the rectangle uniquely). Note that if the part of $R$ to the left of rectangle $[AC]$ is ignored, the remainder is covered by $[AB], [BC]$ and $[AC]$. Likewise if the part of $R$ to the right of $[AC]$ is ignored, the remainder is covered by $[CD], [DA]$ and $[AC]$. Hence the entire $R$ is covered by the five rectangles, with certain overlaps. Each of cells $A$ and $C$ belongs to 3 of the 5 rectangles; each of $B$ and $D$ belongs to 2 of them. (There may be other black cells contained in more than one rectangle.) Hence if $x_1, \dots, x_5$ are the numbers of black cells in the 5 rectangles we obtain $x_1 + \dots + x_5 \ge 995 + 3 \cdot 2 + 2 \cdot 2 = 1005$. This is because the sum counts each black cell except $A, B, C, D$ at least once, each of $B$ and $D$ at least twice, and each of $A$ and $C$ at least thrice. It follows that one of $x_1, \dots, x_5$ is at least $\frac{1005}{5} = 201$. So there is always a special rectangle with at least 201 black cells. Therefore $N \ge 201$ for every configuration.

We tacitly assumed that $A, B, C, D$ are distinct. This can be ensured indeed unless there are no black cells on some two adjacent sides of $R$ except their common corner cell. But then it is clear that $R$ can be covered by at most 3 special rectangles like the ones above, so $N > 201$. (We ignore the trivial case where $R$ has a side 1.)

Now we show an example where $N = 201$. In the second figure the 999 black squares are inside a big $3k \times 3k$ grid square, with $k > 400$. Four groups 1, 2, 3, 4 of 200 black cells each are placed in the corner $k \times k$ squares as shown, in a diagonal-like manner.

Let $X$ and $Y$ be opposite black corner cells of a special rectangle $T$ which contains $m$ black cells. If $X$ and $Y$ are in the same group it is clear that $m \le 200$. If $X$ and $Y$ are in adjacent groups among 1, 2, 3, 4 then $T$ intersects only these two groups. In addition observe that one of the two groups has exactly one cell in $T$ (this is $X$ or $Y$). Thus $m \le 200 + 1 = 201$.

Let $X$ and $Y$ be in opposite corner groups, say 1 and 3. Then $T$ does not intersect groups 2 and 4. Moreover $X$ and $Y$ are the only black cells of $T$ from groups 1 and 3. The remaining ones are all in the central part. Hence $m \le 199 + 2 = 201$. Finally let one of $X$ and $Y$ be in the central group, say $X$. If $Y$ is also there then $m \le 199$. And if $Y$ is in a corner group then $Y$ is the only black cell of $T$ out of the central part. So $m \le 199 + 1 = 200$ which completes the solution.