Some very good responses already. Four more things to throw into consideration; supersets, changing your split, deloads and ongoing nutrition.
Supersets
Rather than doing- exercise A, rest x4, Exercise B, rest x4 etc. Do exercise A, exercise B, rest x4. That way you can give yourself a longer rest period- e.g. a minute, but still spend the same amount of time in the gym because you only rest every other set. If you work opposite muscles in exercises A and B, e.g. bicep curls then tricep extensions then the worked muscle also gets a rest whilst you do the other exercise.
You may find this leaves you less beat up, and still keeps your workouts from getting too long.
One thing I would say though, is don't do it with the big leg movements. Squats, deadlifts etc. really take a toll on your system as the muscles are so large.
Which leads into...
Splits
It sounds like you are doing full body every time. This is perfectly fine. It's how I like to train too. However, if you're doing big exercises for the quads and hamstrings on the same day, that takes a TON of energy. It would be better to split things up into one main leg exercise and some accessory leg exercises. For example squats and calf raises, maybe some light hamstring curls on one day, then deadlifts, tibialis raises and some gentle knee extensions another. You can of course mix it up, but you can see that you're varying the muscles being worked, and especially which ones are being heavily taxed.
Deloads
Don't forget to periodically throw in a deload week where you train much lighter and with lower volume. Your body needs time to recover if you've been continually upping the loads. Some people will do it every 4 weeks, others 6, depends on how you feel. But this could be a big factor you've just hit the point of over training, and your body needs a rest. A lot of bodybuilders will take 2-4 weeks off once a year just to completely let their joints etc recover.
On Going Nutrition
It sounds like you're well aware of the need for good nutrition, but I'd suggest you keep your protein intake up even on days where you aren't training. The body is constantly breaking down and building tissue whether you are training or not. Training obviously stimulates this to happen at a faster rate, but it doesn't stop when the soreness stops (you don't even need to get sore to build muscle- it's a by product not the cause). So to make sure your body always has enough protein- 2.2g per kg of body weight is a good estimate, though if you want a more accurate determination of your needs you could go by lean body mass. The protein doesn't need to be in shakes either if you're sick of them, mix whey isolate or brown rice protein into yoghurt or your cereal, into a fruit smoothie, even into your soup (so long as its flavourful, and maybe not the whey!).
It's also worth thinking about whether you are eating enough calories given all the intense exercise you are doing. Not eating enough is another reason to feel tired.
I use a calorie calculator to work my needs out, as my activity levels do go up and down a bit depending on my schedule. I used to always edit the numbers I got out, based on my knowledge of nutrition/protein requirements, so I spent a few months diving into research on calorie requirements and protein needs and ended up building my own calorie/ macro calculator. It's not the prettiest thing in the world, but I think it's one of the best out there in terms of numbers. Obviously everyone is different, so there will be some small variation person to person, and (usual disclaimers) I'm not a doctor, so use at your own risk, but you can find it here if you're interested:
The World's Best Calorie and Macronutrient Calculator — Kung Fit: Kung Fu and Fitness to stay Fit for Life
Being vegetarian it is possible you may also have an iron deficiency, which can lead to fatigue. It's pretty common, might be worth a trip to the doc.
One last thing to chuck into the mix. If you're main goal is building those shapely muscles, you don't have to go heavy. A recent meta analysis of studies on hypertrophy found that lifting heavy and lifting light had the same effect on muscle building, so long as total work (e.g. reps x sets x weight) was equated. The old dogma of 2-6 strength, 6-12 hypertrophy, 12-20 endurance can be put to bed. The strength and endurance bit checks out, but the hypertrophy happens the same everywhere.
Might take you a bit longer, but lifting lighter weights for more reps might tire you out less.
Hopefully at least some of that is useful for you
Good luck with the training!