Question of legality with tethering? No there isn't. Show me where Verizon says it is "illegal" to tether your phone. If tethering was "illegal", would not the makers of apps like PDAnet and barnacle also be guilty of aiding and abetting a criminal act?Yep .... but they probably could pull something since you have altered the phone out of warranty. There is a question of legality with tethering since we aren't paying for it though.
Now show me where you might be in violation of a contract with Verizon for tethering. If it is in violation of your contract with Verizon then they might have a civil cause of action against you for that, but again it is not illegal.
As to the "aren't paying for it" argument, (opinion begins here) compare that to stealing cable. The latter is illegal because you aren't paying for it. By contrast, I PAY a monthly fee for an unlimited data plan. Whether I send the data I receive on my phone, from that data plan, to my eyes, ears, or laptop is 100% my business and not the carrier's. The language in the contract may differ but, as someone else on here has said, Verizon wants my money and unless I'm running a server on my tethered phone I'm guessing it's quite alright. They already disallow simultaneous voice and data (something AT&T allows; perhaps that's why their network isn't all that great) so my money says they've got the tethering issue under control on their end. And if I do get an extra fine for tethering, I will happily pay it, turn in the phone, and move to another carrier.
On the other hand, if you somehow did not have a data plan and were able to tether your phone w/o being charged, that's a different story.