Lösning hittad av @Dan själv (kunde inte posta på grund av rep)
Lösningen jag hittade på det här problemet var helt enkelt att lägga till nyckelordet "EXEC" i frågan:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Den här lösningen åtgärdade problemet med SQL Server 2005 och fungerade fortfarande med SQL Server 2008 R2.