Um, if you're constantly having to lift the mouse and move it back over then your mouse sensitivity is not high enough. It's easy to get used to a higher sensitivity and remain accurate. I play all day and rarely need to lift the mouse.
I have yet to see anything that can rival the mouse for speed, accuracy, and full range of motion.
Use a joystick to turn? No way you could be as fast and accurate as a mouse user. With a stick, you're selecting acceration rate based on how far you move the stick, whereas the mouse/trackball lets you aim "right here, right now" based on how far you move it. The only thing faster would be a circle that you could press at any point and immediately be facing that direction, but you still have the problem of looking up and down.
I do think using the joystick to move could be very useful. Instead of the on/off keyboard keys, it would be nice to be able to adjust your speed based on how far you push the stick. You could also do trick movement adjustments: full speed forward with a slow/slight left strafe. Can't do that with a keyboard without lifting and re-pushing the keys. Joystick for movement + mouse for aim. Would require some extra coordination though.
I think track-balls are slower than using a mouse because the ball movement ends up not being enough and you have to lift your hand, thereby slowing you down. Now, maybe a gaint trackball (maybe the size of a grapefruit) might be very usefull, but then you have to overcome the weight of such a device.
I can't remember his handle, but there is this Russian (I think) Q3 player who plays with a trackball. He is extrememly annoying to chase-cam because he mostly turns only in one direction (I think it is/was only left). So, if he needs to turn slightly 10 degrees right, he actually spins 350 degrees left to get pointed in the right direction... ugh, makes me dizzy, but he's pretty good.