Using Yaakov's speed-up, I have run his original program with x-grid {m*A + n*B} + {0,A}, and y-grid {m*A + n*B} + {0, B}, for all m,n with |m| <= 4 and |n| <= 4. The program finds no improvement on 3.8 for a generic rectangle, so it looks (to me, anyway) as if this is the best that can be done using this method.

It also looks like we might be able to approach 3.8 arbitrarily closely with concrete examples, if only we had bigger and faster computers.