[bagosm]

Tee hee you used it! Really though, I think there is a big difference between "Very tired" and "exhausted".

Although the technical mind I think is bugged more about precision rather than flow or poeticness of speech Ι think we can appreciate it...

[Zikes]

Especially in certain situations like "I'm not very tired".

Offhand you could say "I'm not overly tired" or "I'm not too tired", but those could subtly change the meaning of what you're trying to say or sound unnatural in everyday speech.

[sliverstorm]

Both of those are modifiers as well, and could fall victim to the same overuse. The only surefire remedy is picking more words that describe a variety of degrees of tiredness.

Tired, exhausted, washed up, worn out, fatigued, beat, weary, run down, depleted...