Perhaps lots of other people have, but I haven't seen basileia written as a nomen sacrum. (I mentioned this to Larry Hurtado and he hadn't either.) I think there is one in POxy 5072. Richard Goode has discussed the Egerton Papyrus's use of basileus as a nomen sacrum (in the 2007 Birmingham conference volume), and I looked at the nice photo in Bell and Skeat, and interestingly the supralinear stroke starts in almost exactly the same place there as it does in POxy 5072 - at the very end of the beta, almost at the beginning of the alpha. The abbreviation is - mutatis mutandis - in the same form as well (BALEUSI in P.Eg. and BALEIA in the text below).
Check out line 9 of POxy 5072:
(It's one of the images posted by oxy.ac when they publicised the open access of the papyri images. It'll be the first in the next POxy vol.)