In fact, I will show that it is not possible to fully infect any n x n board with n-1 initially infected. Here is my proof:
Consider the case of an infinite grid, with a finite number k of initally infected cells. I am going to show that the maximum possible area that can be infected by these cells is k^2.
Theorem 1: The end result of any initial infection configuration will be a collection of non-adjacent, full, rectangular regions.
For two rectangles to be non-adjacent, they cannot overlap, touch at the corners, or have any single non-infected boundary square in common.
Proof of Theorem 1: For Theorem 1 to be false, we would have to find a rectangular region that was not full, or two full rectangular regions that were adjacent.
The first case is not possible: for a rectangular region to be not full, we would have to locate a 2x2 region with either one corner missing or two non-adjacent corners missing. By the rules of infection, such a 2x2 region could never exist as an end state.
The second is also not possible. If two rectangular regions overlapped, they would form a non-full rectangular region, which we just said is impossible. If they were adjacent and shared a boundary cell, that boundary cell would become infected and make a non-full rectangle, which is impossible.
Proof by contradiction, Theorem 1 must be true.
Theorem 2: A full m x n rectangular region must contain at least [ (m + n) / 2 ] initially infected cells.
Note: [ x ] is the least integer function
To prove this, I will use the following fact: The end state of any initial infected configuration is unique. Since the process of infection is a strictly increasing operation on the number of infected cells, it matters not the order in which we apply the rules of infection, nor when the initially infected cells are introduced - we will still get the same unique end result.
Now, consider a fully completed m x n rectangle, based on an initial infection configuration. Any initially infected cell that can be removed without affecting the end result is considered superfluous, so we will ignore them. The rest of them, the essential ones, are the important ones. If we remove an essential initial infection cell and construct the new end result, we will be left either 1 or 2 rectangles that satisfy Theorem 1. 3 is impossible, because the removed initial infection cell would have to be adjacent to all 3, which is impossible without two of them being adjacent to eachother.
In the case of 1 rectangle, the new dimensions are m' x n'. Now, how many dimensions can we add to the m' x n' rectangle by attaching a single, new initially infected cell?
If you place the new infected cell inside the rectangle, the answer is 0: m' x n' stays the same, and the new cell is superfluous. If you place it adjacent to one of the edges, the total dimensions will go up by 1, because you'll add either 1 row or 1 column. If you place it at a corner, the dimensions go up by 1row + 1column = 2, and if you place it two spaces away from one of the sides, the dimensions will go up by either 2 rows or 2 columns. Any further away, and the rectangle does not change, making it an instance of the next case. Either way, the maximum increase of m' + n' is 2.
In case 2, there are two rectangles to worry about: a x b and c x d. We want to add an initially infected cell to them in order to obtain the greatest possible difference of ((m' + n') - (a + b) - (c + d)).
Let a' x b' be the new dimensions of a x b when adding the initially infected cell, while ignoring c x d. Let c' x d' by the converse case. The maximum of (a' + b' - a - b) is 2, as we showed previously. The same is true of (c' + d' - a - b).
Now, how can we maximize m' + n' based on c' and d'? The optimal case, intuitively, is when a' x b' and c' x d' share a single row and column: no more. Since they must share at least one cell, they must also share a single row and column. If they share more, it decreases m' and n'.
In this way, m' = a' + c' - 1, n' = b' + d' - 1, and the maximum difference is: ((m' + n') - (a + b) - (c + d)) = (-1 + -1 + (a' + b' - a - b) + (c' + d' - c - d)) = -2 + 2 + 2 = 2
And voila, Theorem 2 is proven! By induction, if an m x n rectangle has [ (m + n) / 2 ] initially infected cells, then by adding a new cell, we can only increase the dimensions by 2, increasing the [...] quantity by 1 - which verifies the claim. Similarly, if we take two rectangles with initial quantity [ (a + b) / 2 ] + [ (c + d) / 2 ], we can only increase the quantity by 1 and the total dimensions by 2 with a new cell, also verifying the claim.
To get the greatest ration of initial cells, [ (m + n) / 2 ] to area m*n, simple symmetry will tell you m = n, making a square. For k initial cells, the maximum area therefore is [ (k + k) / 2 ] --> k*k = k^2
Ergo, impossible for a 12x12 board to be infected with 11 cells
QED
@ugly_zeke: You're definitely right, nice job.