Unless I'm grossly misunderstanding your structure, a simple join should work fine:

SELECT stories.vid, body, timestamp, COUNT(votes.id) votecnt FROM stories
INNER JOIN votes ON stories.vid=votes.vid
WHERE stories.lv=1 AND stories.status=1
GROUP BY votes.vid
ORDER BY votecnt DESC

I'm not sure what you mean by

It would be even better, if the first query would sort the table by status = 1 count at first, and then total votes.

since your where statement only uses votes/stories that have status=1.

What is funny about temporary tables in a stored procedure is not so much the transient existence of the table (which gets dropped upon the DB connection's termination), but the scope of the stored procedure.

Someone asked this question on StackOverflow : Scope of temp tables created in MySQL stored procedure. It has been over a year and nobody answered the question? Let me set the record straight. The fact is: The temp table exists inside and outside of the Stored Procedure, but you can do things with the temporary table only inside the scope of a running Stored Procedure.

According to the Book

Chapter 5 has a subheading Returning Result Sets to Another Stored Procedure.

It says in paragraph 2 on Page 117:

Unfortunately, the only way to pass a result set from one stored procedure to another is to pass the results via a temporary table. This is an awkward solution b, and -- because the temporary table has scope throughout the entire session -- it creates many of the same maintainability issues raised by the use of global variables. but if one stored program needs to supply another stored program with results, then a temporary table can be the best solution.

Looking back at the StackOverflow question, I can see someone called the Stored Procedure from the mysql client. Since the mysql client is not a Stored Procedure, the results cannot be manipulated the mysql client level via DML other than doing a SELECT to see the results. Since you calling a recursive stored procedure, you can rest assured the temp table is fully accessible for the duration of the DB Connection.

I hope this answers your question.

UPDATE 2014-01-31 11:26 EST

In your last comment, you said

If we employ persistent connections, will the MEMORY table persist through multiple REQUESTS, and it seems it will, so for performance sake, I'm assuming that using this method will *REQUIRE us to explicitly DROP the temporary MEMORY table. Do I assume correctly?

Yes and No. I say Yes because it is one way to do it. I say no because another way to do it is:

CREATE TEMPORARY TABLE IF NOT EXISTS id_list (iid CHAR(32) NOT NULL) ENGINE=memory;
TRUNCATE TABLE id_list;

Whichever way you choose, the operation is still the same since TRUNCATE TABLE drops and recreates the table. This will not harm other DB Connections since each Connection has its own id_list table.