Oplossing gevonden door @Dan zelf (kon niet posten vanwege vertegenwoordiger)
De oplossing die ik voor dit probleem vond, was simpelweg het trefwoord "EXEC" aan de zoekopdracht toe te voegen:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Deze oplossing loste het probleem met SQL Server 2005 op en werkte nog steeds met SQL Server 2008 R2.