Caerlaverock (Castle of the Lark), near Dumfries. I've been there a few times, and Wiki gives a pretty good history/description. There was an earlier castle a few hundred metres away, which was probably abandoned because of marshy ground, and the foundations are still visible, + the remains of a Roman camp and British Hill fort nearby.