I always assumed it had more to do with him smuggling goods into federation colonies or some such. He's a very good pilot because he knows how to slip between the cracks of sensor fields and how to use unconventional maneuvers to throw off anyone chasing him. Sounds like the behaviour of a smuggler to me.
Also, I'm pretty sure the pitch for Tom Paris was basically "Han Solo but Star Trek".