Solução encontrada pelo próprio @Dan (não foi possível postar devido ao representante)
A solução que encontrei para esse problema foi simplesmente adicionar a palavra-chave "EXEC" à consulta:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Essa solução corrigiu o problema com o SQL Server 2005 e ainda funcionou com o SQL Server 2008 R2.
