I've been working on the word rectangle problem, too. Care to share your '7x7 in 60-ish seconds' solution? Or at least some hints on how you approached the problem? I'd be much obliged, as they say.
I agree that tries are good. There is also an 8x8 solution if you wait long enough. Strangely there don't seem to be any non-square solutions up to the sizes I was able to check, so you might as well search only for squares, which speeds it up a lot. I'm not sure if I should post a solution but I'm happy to email it to you.