rather than looking at recompiles and statistics, how about looking at your joins themselves.

would it be possible to have 2 versions of the proc - each with distinct join hints

one usign loop joins and the other using merge or hash joins. this would avoid the constant recompiles.