I too had a vegetarian "phase". I was vegetarian for 3 years, starting with being vegan for about 6 weeks. Trying to be vegan, I felt like I wanted to die every day. Constant bloating, digestive problems, aches and pains, no energy, etc. I was constantly craving foods and eating a lot of extra calories all the time.
I started adding in foods to see what would help, and in retrospect (knowing what I know now about nutrition), it was all protein and animal fats: eggs, cheese and seafood. I called myself "vegetarian" even though I ate these things.
This diet kind of worked for a while, though it was a hassle to find eggs and seafood for most meals. I learned (the hard way) that I need protein with almost every meal. If I skip protein, I get onto an energy / blood sugar roller coaster. I did this for a couple of years, thinking it was "normal", but in retrospect I was probably doing damage to my body.
Finally one day I was playing volleyball and a friend of mine was grilling london broil on a grill. I just couldn't take my eyes off of it. When he offered me some, I ate about a pound of it, and felt like someone had given me a shot of go-fast juice. I had great energy for the rest of the day, rode my bike home, slept great, and have been an omnivore ever since.