Solution trouvée par @Dan lui-même (impossible de publier à cause du représentant)
La solution que j'ai trouvée à ce problème était simplement d'ajouter le mot-clé "EXEC" à la requête :
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Cette solution a résolu le problème avec SQL Server 2005 et fonctionnait toujours avec SQL Server 2008 R2.