Løsning fundet af @Dan selv (kunne ikke skrive på grund af rep)
Løsningen, jeg fandt på dette problem, var simpelthen at tilføje søgeordet "EXEC" til forespørgslen:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Denne løsning løste problemet med SQL Server 2005 og fungerede stadig med SQL Server 2008 R2.