I'm not particularly experienced with proofs, but I think I have an idea of why (the number given in other answers) is minimal for the question asked:
Because the board is a square and the side length is a power of two, a line running through the midpoint of the side will never pass through a cell (always between two cells).
No matter which cell Alice removes, it will always be in one quadrant of the board. Similarly, no matter which position Alice asks for it to be in when reconstructed, it will always be in one quadrant of the board. Because Bob can rotate and flip the pieces, the remaining three quadrants are irrelevant and can be removed as a single piece.
This means that:
The board is now a 4 x 4 board, square, with a side length that is a power of two. Again there a line dissecting the board perfectly in half will not pass through any cell, horizontally or vertically, but always between two cells.
No matter which cell Alice removes, and where she requires the hole to appear in the reconstructed board, it will always be in one quadrant. The remaining three quarters of the smaller board are irrelevant and can be removed as a single piece.
This can continue until:
The cell removed represents one quarter of the remaining board (in this case, this is at this point, however on a larger board, this process would continue, similarly, if Alice cut a 2 x 2 piece from the board, this would occur after removing the first three quarters of the board). When the cell removed represents one quarter of the remaining board, this piece may be rotated or flipped into whichever orientation is required.
The cell removed...
Represents one sixty-fourth of the original board, and one quarter of the final piece. One sixty-fourth is one quarter cubed, which is I think the reason that three is minimal.
This approach could be scaled for any board size...
So long as the side length is a power of two times the side length of the cell(s) removed. I'm not sure how of how this would need to be changed if the board was rectangular, or if the side length was odd, for example (although I suspect it will be the largest integer number of cells less than half the rows/columns, so just slightly less than three-quarters, when removing pieces).
As I said, I'm not experienced/adept at proofs, but this seems to make sense as to the reason. Perhaps someone else can double-check my working?
This is perhaps analogous to:
A guessing game, where the approach taken is to halve the possible range (assuming you're told "higher" or "lower") and then doing the same again, until reaching the number. In this case, we are constantly narrowing the cell location to a quarter of a quarter of a quarter (and so on, in the case of a larger board). As each piece is placed, it is rotated/flipped to position the empty space remaining in the correct quadrant of the quadrant being partially filled by the newest piece. This means that we are only able to section off three-quarters of the empty space at a time, which is why the cell(s) removed will represent a quarter of the square around the smallest piece.