nightcrawler,
I think that may be a viable solution. My concern was with statement such as: "SELECT * FROM ( EXECUTE PROCEDURE xxx()) t". In such case, the query engine needs to know the data types of the stored procedure output to process the query.
If my understand your suggestion correctly, then we will have two types of stored procedures. One type (the existing type) has predefined output parameters, and a new type that has no predefined output. The new type of stored procedure, the ones that has undefined output, will not be allowed in place of table input like the sample statement above.

Alex,
I'd not pre-define the output parameters. Given the case that you want to create some kind of temp table inside the stored procedure to make some fancy stuff like a Pivot table - there's no way to predict the output parameters. They could be that different, dependant on the data, not on a structure.
What about defining the output table if wanted and just give that back if no SELECT (or EXECUTE PROCEDURE) was the last of the statement?
iow if no output cursor was given, do an implicit "SELECT * FROM __output".

We need some clarification on this.

Are the output parameters still needed to be defined? I think that the answer is yes. And the select list of the last statement must match the output parameter list of the stored procedure.

I second that.

very much needed!