Legend in caption

At one point I had a situation like you describe. What I ended up doing is putting the legend so that it juts out a little and fiddled with the boundingbox of the resulting figure so that it remains the same as when the legend does not jut out.

I wrote a "script" that steals the BBox of one .eps file and plops it into another:

#!/bin/bash
#take the bounding box of the first argument, and plop it into the second.

BB=`grep %%BoundingBox $1`
sed "s/%%BoundingBox.*/$BB/" $2 

This script simply outputs the resulting .eps file to stdout. if you want to direct it to a third file you'd use it like so:

% copyBB goodBB.eps niceLegend.eps > combined.eps

(It's a bash script, sorry windows users...but then, it isn't so complicated...so you could re-implement it for your shell.) Caveat Empor! I did not test this for many cases. My use-case was as follows: create two versions of the same figure, one with the correct bounding box, and one with the legend jutting out (upper right corner, in my case). Then, I use the script to steal the BB from the "clean" figure and place it onto the legended one. This allowed me to align figures more easily than otherwise (in my case I also wanted to signal that the same legend can be used for the four figures):

(The lower left figure was created using copyBB, the remaining 3 were unmodified)