SQL 2005 Unused procedures
What you are looking for is not really possible, at least not in the spirit of what you are ultimately trying to accomplish. As I explained in my answer on what is pretty much a duplicate question -- Query last time a view, funcion or sp was last used/read -- this approach doesn't take into account infrequently accessed code paths in the app code and "support" code that is executed manually, usually in SSMS. It sucks, but you really just need to do an exhaustive review of all code that could be executing Stored Procedures, as well as support tickets that include instructions on what to run in case of X, or even internal wiki pages that might have instructions indicating to execute Stored Procedures (or use UDFs, etc).

Also, you can create a table to log usage, and for those Stored Procedures that you believe are "unused", add a line at the top to insert into this log table. Check that log table periodically, and set a cut-off time with your team / department where everyone feels comfortable getting rid of that code if it hasn't been accessed within that amount of time.

P.S. I have gone through this process before. And I have had support people call me (or my manager) shortly after a release because I had dropped some code that was not referenced in any other code or internal wiki page, etc (and believe you me, I was quite thorough in my research!). BUT, it was being used in a Microsoft Access app that a support engineer created years prior to make certain support tasks / requests take less time (i.e. not needing to wait 2 weeks for a DBA to get around to running the Stored Proc so that a customer could do what they needed to do). And since none of us database engineers was aware of this app even existing (it was only on a few desktops in the support area, and certainly not in SVN), it made it a bit difficult to take into account.

P.P.S. regarding this statement:


  I'm aware that this will only show procedures which have been used post restart. 


That is the most that can be shown. But, a restart is not the only way to clear cached system data. Either of the following commands will also clear that data:

DBCC FREEPROCCACHE;

DBCC FREESYSTEMCACHE('ALL');


AND, SQL Server will periodically dump the cached data when there is memory pressure (i.e. low available physical memory).

Hence, you cannot use the output of any of the DMVs / DMFs for this purpose.

P.P.P.S. The sys.dm_exec_query_stats DMV works at the server / instance level, not the database level. Meaning, not only do you not need to wrap such queries in sp_MSforeachdb, but you don't want to do that anyway since the same result set will get repeated per each of your databases.

P.P.P.P.S. The sys.dm_exec_sql_text DMF that you are already using conveniently returns columns for objectid and dbid. The dbid column can be used along with the DB_NAME() built-in function that you are already using to get the "current" database name for that query. And, both the dbid and objectid columns can be used along with the OBJECT_NAME() built-in function to get the name of the stored procedure, relative to that "current" database (as opposed to the database that you are running this query in, which can return erroneous values since the objects are potentially not in that database). And then both of those functions can be used again in the ORDER BY clause.

Taking all of that info into account, the re-written query is:

SELECT  DB_NAME(qt.[dbid]) AS [DatabaseName],
        OBJECT_NAME(qt.[objectid], qt.[dbid]) AS [SP Name],
        qs.execution_count AS [Execution Count],
        qs.max_logical_reads,
        qs.max_logical_writes,
        qs.creation_time,
        DATEDIFF(Minute, qs.creation_time, GetDate()) AS [Age in Cache]
FROM    sys.dm_exec_query_stats AS qs
CROSS APPLY sys.dm_exec_sql_text(qs.[sql_handle]) AS qt
ORDER BY DB_NAME(qt.[dbid]) DESC,
         OBJECT_NAME(qt.[objectid], qt.[dbid]) DESC;