Renaming Sql Server database unusual result
What SQL Server is doing is, it is caching the query plan for 

 exec [Database_A].[dbo].[TestSP]


This can be found using :

SELECT 
    usecounts, cacheobjtype, objtype, text 
FROM 
    sys.dm_exec_cached_plans 
CROSS APPLY 
    sys.dm_exec_sql_text(plan_handle) 
WHERE 
    usecounts &gt; 1 AND text LIKE '%TestSP%'
ORDER BY 
    usecounts DESC;
GO


When you execute your stored procedure during step 1, 2 or 3, it gets cached in the procedure cache.

Hence during your 4th step, it throws an error.

If you do a dbcc freeproccache, and then rerun the SP exec [Database_A].[dbo].[TestSP], it will work.

As @Aaron pointed out, it will work using EXEC sys.sp_refreshsqlmodule 'Database_A.dbo.TestSP' or recompiling the SP sp_recompile TestSP  as well.

Ref: http://technet.microsoft.com/en-us/library/bb326754(v=sql.105).aspx

There is no need to restart SQL Server.

Note: Free ProcCache will flush out all the query plans, so its better to use sys.sp_refreshsqlmodule or sp_recompile.