I like to beat dead horses, so I'll chime in with the food allergy route. Gluten caused constant fatigue for me (and it's in EVERYTHING!). Within a week of going completely off it, I was feeling ten times better. My post history in H&F was littered with failed attempts to get motivated & follow a program, but I just never had the energy to keep it up consistently. Now, no problem. I sleep 6 to 8 hours a night, feel good, and I'm not tired & fatigued all the time. Huge lifestyle difference.
How much are you willing to cook? I'm into freezer meals for convenience. Read through this thread:
http://forums.anandtech.com/showthread.php?t=2336038
That's pretty much what I do, make a bunch of food ahead & then microwave it at work. There are some tricks you can do to make things taste better reheated, like using sauces (ex. Prego on top of chicken, which keeps it moist when microwaving), spices, etc. Also, getting protein on a vegan or vegetarian diet is not a problem, plenty of options - egg protein, hemp protein, yellow pea protein, etc. if you want to go the powder route for smoothies & stuff. Smoothies are an easy way to do breakfast & snacks:
http://catch42.pbworks.com/w/page/78032378/Protein Smoothies
I have a shaker bottle (has a blender ball inside) & will have a mid-morning smoothie at work sometime, if not for breakfast. Or even for dessert. For example, I've been experimenting with avocado drinks a lot lately (sounds gross, but I had an amazing avocado "boba" smoothie at a Vietnamese place recently, and I'm hooked!). I'm drinking one right now: one medium avocado, a couple spoonfuls of hemp hearts (I like using the seeds better than the protein powder usually, tastes better & not grainy), some sugar, vanilla rice milk, an extra dash of vanilla extract, and ice. It's kind of similar to a milkshake, tastes great! (that is, if you like avocado...and even then, sweet avocado sounds weird, but it's actually pretty good!)
Anyway...number one, fix your fatigue problem. It might be food, or it might be something else like a thyroid issue like Magnus said. Elimination diet is the way to go. Or just quit eating for a day (do a food & drink fast for 24 hours) & see if you feel less horrible the next day. As far as food allergies go - do you wake up groggy? (that's a big sign) Do you have dark circles under your eyes? (those are called "allergic shiners" - I always thought they were from not getting enough sleep, but as it turns out your eyes get puffy from lack of sleep, and dark from food allergies, typically). After that, figure out your diet. Here's the currently one I'm loosely following:
http://catch42.pbworks.com/w/page/78929159/Meal Plan
I got hooked on the eating multiple small meals a day thing a few years ago; I love food, I love eating, and it keeps my energy up to eat smaller meals more often. I also like dessert, so not only do I have dessert (healthier options too!), but also treats throughout the day. Energy bites are really easy - you don't have to bake them, and they're basically like fresh little balls of granola bars:
http://catch42.pbworks.com/w/page/84297007/Energy Bites
Smoothies are easy for breakfast - throw in some fruit, a banana, ice, and protein powder, and you've got your fiber hit for the day plus some protein to round out the sugar hit (plus the sugar hit isn't as bad since you're blending a whole fruit, which has fiber to balance it out). My mid-afternoon goodies are excellent as well, like the Snickers bar (no refined sugar, tastes AMAZING!). Only thing I'm really lacking right now is my sleep schedule, between work & family and bad habits, I'm still not going to bed early very often haha.
If you have any questions about food allergies, fire away. There are a few of us here with them. Diagnosis can be a tough process (it's more of an art than a science) & the first year of adjusting is usually pretty rough, but after that it's mostly a cakewalk once you get the hang of it. Plus I'm far more health-conscious now because I know what I'm eating!