Firstly the penalty rushing is something the everybody does. The Paraguay penalty was where the ref probably became aware of the rushing, after he awarded the goal, and pretty much decided to get harsh on it. The Spain penalty was not taken again because of Paraguay rushing the box, but because Spain rushed it. [-]Technically he got it wrong, it should have been a free kick to Paraguay, not a retake, but that's beside the point[/-] He got the retake right. Old rules was a free kick to Paraguay. Spain cost themselves the goal, by making the ref aware of their encroachment with the first penalty. I personally think the ref only clicked on the rushing after he had awarded the goal.
Then the Valdez goal, it was very definitely offside. However it was not him who was offside. I can't remember offhand who the other player was, but he was the one offside, and he was the one flagged. Although he did not touch the ball, he is still very much offside. He made an attempt the play the ball, from an offside position, and affected the run of play. By making the attempt, he pulled defenders towards him, which could have been marking Valdez, and thus gave his team an unlawful advantage. Thus the offside. As passionate as you want to be about that, it was offside, by all standards. If you were listening to the commentator on SABC1, he got that very wrong, however the experts at half time pointed out his mistake.
So I don't think Spain should be branded a cheat. If you look at almost every side, they are guilty of rushing the penalty box. If you want to get sticky about stuff like that, technically the keeper is not allowed to move off of the goal line until the ball is actually kicked, but almost every single keeper moves as the striker plants his left foot, and they invariably move forward, so technically almost all penalties in the modern games would need to be retaken.
My opinion, and interpretation of the rules of the game.