Solution:

Given an $m \times n$ grid, the number of tokens placed on the vertices of the grid is $(m+1)(n+1)$, while the number of tokens placed at the center of each cell is $m n$, so that the total number of tokens is
$$N = 2 m n + m + n + 1.$$
We observe that
$$2N - 1 = 4 m n + 2 m + 2 n + 1 = (2m + 1)(2n + 1).$$
Since $m \geq 1$ and $n \geq 1$, we have $2m + 1 \geq 3$ and $2n + 1 \geq 3$; and hence we deduce that the solutions correspond to the decompositions of $2N - 1$ as a product of two odd numbers greater than 1. If $N = 500$, $2N - 1 = 999 = 3^3 \cdot 37$, such decompositions are
$$N = 3 \cdot 333 = 9 \cdot 111 = 27 \cdot 37 = 37 \cdot 27 = 111 \cdot 9 = 333 \cdot 3$$
and therefore the pairs of numbers $(m, n)$ relating to question (a) are the following:
$$(1,166),\ (4,55),\ (13,18),\ (18,13),\ (55,4),\ (166,1)$$
To answer question (b), we show that, if $2N - 1$ is prime, then there exist no grids with exactly $N$ tokens. Indeed a prime number cannot be written as a product of two integers both greater than 1.