With regard to procurement legislation, is it legally permissible to require bidders to be in possession of an ISO9000 certificate?

Yes. Regulation 19(4) explicitly entitles utilities to have this certificate, with the regulation offering provision for service providers to provide a certificate in order to show that they conform with BS/EN/ISO 9000, or the national equivalent from their native country.