The answer is $43$. Proof of minimality: for some given method to delete sticks, consider putting a piece on the board which is only allowed to move to an adjacent grid with no stick in-between. Grids are then divided into *blocks*: two grids are in the same block iff the piece can reach one from the other by a sequence of moves. Observe that every deleted stick belongs to exactly one block. The critical observation is that a block consisting of $n$ squares contains at least $n-1$ deleted sticks. The idea arises from the famous theorem in graph theory that the number of edges in a non-empty connected graph is no less than the number of vertices minus $1$. Also observe that blocks of $1,2$ grid(s) must contain at least $1,2$ deleted stick(s), correspondingly, to avoid rectangles. Therefore we verify that $$\#[\text{number of deleted sticks in a block}]\geq \frac{2}{3}\#[\text{number of grids in that block}]$$ thus the total number of deleted sticks $\geq 8\times 8\times\frac{2}{3}=42\frac{2}{3}$. Therefore it must be at least $43$.

Construction: we follow the above theorem. Let's place a single square in the corner (with one edge deleted), and $L$-s (the pattern consisting of three squares but not a rectangle) elsewhere. There is a famous recursive pattern and it is easy to verify it works. The same goes for all chessboards with edge length a power of $2$.