"Solicitó formalmente" como tú sugieres también funciona bien.

Suerte.

al Dep. de Justicia para que revocara la orden de comparecencia / anulara la citación.

Creo que la palabra "petición" implica por sí la formalidad/oficialidad de la solicitud, pues normalmente es un escrito. De todas formas, puede añadirse "formal".

Ejemplo:
29/10/2013 - ... dijo que los padres de éste enviarán durante las próximas horas una petición formal al Departamento de Justicia para que se examine si la ... (http://www.telemundo51.com/content-center/Piden-que-se-revis...

6/2/2014 - Adelson y su equipo han enviado a todas las fiscalías generales de dicho país una petición al Departamento de Justicia para que retiren la ... (http://www.codigopoker.com/2014/02/06/el-poker-online-en-est...

Me parece una traducción correcta y la más obvia.
"Capriles solicitó formalmente el recuento voto a voto" http://www.diariopopular.com.ar/notas/153620-capriles-solici...

“Acabamos de solicitar formalmente la convocatoria de una reunión de Unasur, la cual ha tenido una buena receptividad por parte del presidente de Surimam”,
http://acn.com.ve/venezuela-solicito-formalmente-a-unasur-un...

"Snowden solicitó formalmente asilo político a Nicaragua"
http://www.lagaceta.com.ar/nota/551618/mundo/snowden-solicit...