Some notes too big to put into a comment (though this doesn't suggest an obvious algorithm):
The punch line (EDITED): At least two vertices of the maximum area rectangle must lie on the boundary of the polygon (i.e. along an edge, or at a vertex). And if the maximum area rectangle is not a square, then at least three vertices must lie on the boundary of the polygon.
I proved it to myself in four steps:
Note #1: At least one vertex of the maximum area rectangle will always lie on the boundary of the polygon. This is pretty obvious, but a proof could go like this (by contradiction): Suppose you had a "maximal" rectangle with no vertex on the boundary of the polygon. That means there would be at least a little room around each of its vertices. So you could expand your rectangle a bit, contradicting its maximality.
Note #2: At least two vertices of the maximum area rectangle will always lie on the boundary of the polygon. A proof could go like this (again by contradiction): Suppose you had a "maximal" rectangle with only one vertex on the boundary (guaranteed by Note #1). Consider the two edges not adjacent to that vertex. Since their endpoints are NOT on the boundary, there's a little room around each. So either of those edges could be "extruded" a bit, expanding the polygon's area and contradicting its maximality.
Note #3: There are two diagonally opposite vertices of the maximum area rectangle that lie on the boundary of the polygon. (We know from Note #2 that there are at least two, but not necessarily that they're across from each other.) But again by contradiction, if the only two boundary vertices were adjacent, then the opposite edge (neither of whose vertices are on the boundary) could be extruded a little bit, increasing the area of the rectangle and contradicting its maximality.
Note #4: (EDITED) If the maximum area rectangle is not a square, then three of its vertices will lie on the boundary of the polygon.
To prove, suppose that's not the case, i.e. that the maximum area rectangle is not a square, but only two of its vertices are on the boundary of the polygon. I'll show how to construct a bigger rectangle, contradicting the maximality.
Call the vertices of the rectangle
D. Without loss of generality, assume that
D are the two that are on the polygon boundary. Since
C are on the interior of the polygon, there's some wiggle room around them (represented with circles around
C in the picture below). Now draw a circle around the rectangle, and slide points
C a little bit around the circle by the same amount (to make
C', pictured below) so that the new rectangle
A'BC'D is more square than the original rectangle. This process creates a new rectangle that is also within the original polygon and has a larger area. This is a contradiction, so the proof is done.
To believe that proof, you have to convince yourself that the area of a rectangle inscribed in a circle increases as it becomes "more square" (i.e. the difference between the edge lengths gets smaller). You also need the polygon to be convex so that the new lines are all within it. And there are probably other little details getting swept under the rug, but I'm fairly sure they all work out.