Very nice! I also took a bitwise approach and ended up with something that solved all possible puzzles in 5 seconds (in 60 lines of matlab).
A technique I used that helped bring the time down was to calculate the points for a given puzzle irregardless of the center letter. This provides an upper bound for the points that could come from that puzzle. After you've done that for all the boards, you sort by upper bound and then start calculating the actual scores for the different center letter options. Doing this for the 538 puzzle, I only had to look at center letters for the top 2 puzzles 'aeginrt' and 'adeinrt' (after those you find a score that is greater than the upper bound for any of the other puzzles).
