Lösung von @Dan selbst gefunden (konnte wegen Repräsentanten nicht posten)
Die Lösung, die ich für dieses Problem gefunden habe, bestand einfach darin, das Schlüsselwort "EXEC" zur Abfrage hinzuzufügen:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Diese Lösung hat das Problem mit SQL Server 2005 behoben und funktionierte weiterhin mit SQL Server 2008 R2.