The penalized least squares interpretation of the classical random effects estimator suggests a possible way forward for quantile regression models with a large number of fixed effects. Sparse linear algebra and interior point methods for solving large linear programs are essential practical tools.
This paper appears in 2004 in J. of Mult. Analysis, 91, 74-89.
A very basic version of the software is available here. Note added October 26 2010: It is now possible to do what is done with this code much more easily using the package rqpd available from R-forge: here. In the context of the usual quantreg package some functionality is provided by the function rqss(). The fixed effect parameters can be introduced in the usual R way via a factor variable, and the shrinkage, if desired, can be imposed with the lasso penalty method. See ?rqss for further details. The paper is available in pdf.
Comments are, of course, always welcome.