Thank you again for the comments.
The main issue with the outlined look is how to make the purpose of structures within a level obvious. In DOOM you can tell if a "wall" is a door, lift, switch or other special feature by its texture. I suppose there are other ways to make these features more obvious - the crosshair changing into a hand when looking at something interactive or a sprite near the thing as a sign, say.
Looking up or down is done in the style of Heretic or Duke Nukem 3D ("y shearing") - all it's doing is shifting the viewport up or down in 2D. The further you look up or down the more distorted walls appear (you'd never be able to look straight up or down, for example) but it's better than nothing.
I haven't had any more time to work on the project recently but did have a shufti at the inner workings of DOOM for "inspiration". One trick I had missed is to store the angle of each wall in the level data. This allows you to very quickly perform rough backface culling, as you can compare the wall's angle with the current view angle to determine whether it's facing away from you entirely or not (I currently clip and project each wall in turn to determine which side you're on). Due to perspective projection I don't think this will be completely reliable (a wall that is perpendicular to the projection plane would show one side if it was on the left of the screen and the other side if it was on the right of the screen, yet still has the same angle) but it may be a way to quickly discard walls that more obviously have their backs turned to you.
Another trick is to store a bounding box for each node of the BSP tree. If this bounding box is outside the field of view then that node and all of its children can be ignored.
As with all potential optimisations you do of course have to ensure that these additional tests (such as the bounding box for BSP tree nodes) don't take longer to perform than the chunks of code they're attempting to avoid having to run. In some instances they may make simple levels run slower but make larger levels run much faster, so it'll be interesting to see what happens...