Es un poco jodido porque, tal como comentas, el marcado se pierde con el enlace. Quizás si dotas a esos enlaces con la capacidad para hacer un $_POST, podrías lograr el objetivo. La forma más sencilla es con JQuery, además de accesible porque no es necesario añadir el atributo onclick. Con una pequeña función inicial capturas clases, id, etc. y le asignas la característica que desees.
Otra vía que se me ocurre es la de establecer cookies, pero creo que igual debes hacerlo con javascript porque (dado que la paginación se hace mediante enlaces) es necesario que capture los checks en tiempo real.
Otra opción también tiene que ver con javascript y consiste en construir una paginación "falsa" como ésta:
http://www.frequency-decoder.com/dem...ited/paginate/ . Nunca me han gustado los scripts que cargan todo de golpe, pero en tu caso podría servirte (por ejemplo, si el conjunto de datos no supera las 20 o 30 páginas).
Mi recomendación es que le metas JQuery y conviertas esos enlaces en inputs de tipo submit.