The problem has finally been solved by Matthew Scroggs.
He and I, independently, found a counterexample for the conjecture by replacing lowest common multiple by greatest common factor using the relation: 
In 15×5, there are 26 filled squares and gcd(15,5)=5, so 15×5 is a counterexample to the conjecture!
As it turns out, SAGE is giving float(26/5) = 5.0 when I run it inside the program, but return 5.2 when I run it independently. Leading to wrong conjecture.
The solution is pretty beautiful and this is the outline:
There are 3 levels of simplifications of the problem:
Original Grid –> Dual Grid –> Mirror Grid –> Inner-point Grid
Counting the “Corners visited twice” (the subtracted term) was something I wasn’t able to do. Corners visited was essentially what I called “number of steps needed for algorithm to stop“. So, his mirror argument provides a proof without words of that result.
Gaurish4Math 