If you reach really low or the bottom of a virtue, can you eventually bring it back up?

I would think so. Can't see why not.

Might not be especially fun, but I don't think you become permanently "banished" or w/e. Why do you ask? Have you randomly been killing people?

No, mostly raiding the King's Vault

Been working hard to raise my honesty... but feel I am not making any progress...

No you can't drop your virtues so low that you can't bring it back up but depending on how nasty you have been it will sure as hell feel that way as you will have to grind like hell to get it back up.

Yes you can

Depending on the virtue you must be super vigilant

honesty - always pay for your reagents, dont steal

compassion - give to beggers, give blood at healers

etc

yes.
however, the only even vaguely tempting/compelling "jerk first, Virtuous later" advice i have ever seen is the 1) buy a full stack of each reagent for 1g each, 2) buy back the damaged Virtues by overpaying 1g for one reagent at a time.

...and this despite the fact that unless you are seriously dragging the game out* - say, by bringing all seven companions to level 8 and/or sweeping every room on every level of every dungeon, or soloing and/or overcompensating with a lot of flashy magic - there's really no need for a full stack of anything other than maybe Garlic & Ginseng.

* or you have a hard-on for air travel and very bad luck/timing with Wind control xD

one thing to consider is 'voting up' the harder-to-come-by virtues other than your 'class virtue' during the initial 'virtue tarot' reading; you pretty much have to actively work against Honor (there are a variety of ways to do this, but so many actions give bonuses it's ridiculous), Valor (perhaps by fleeing from non-evils) or Spirituality (by bungling the mantra), and Humility is really not a challenge unless you 'can't help' roleplaying arrogance, in which case you basically will not finish the game... and really, giving 1g to every beggar on a tour of Britannia will net you dozens of Compassion pts. - ditto for Sacrifice in donating blood to every Healer.
that leaves Honesty (and though i comprehend the urge of Going Shepherd for the sheer challenge of a magic-less leader + hanging around swamps with no healers (let alone money for healers), i'll never stop preferring the Mage) and Justice... and Justice will go up with Valor and Compassion as you consistently refuse to retreat and refuse to be aggressive towards non-evil.

You always lose Valor from fleeing any fight, but if you flee from non-evils, other virtues go up. Those will also go up if you can get the non-evils to flee the map safely, and you won't lose Valor. I think that's how it works...

I think Humility might be hard to raise back to an acceptable level. Picking the "right" or "wrong" answer is a little vague, especially since they don't show a pop-up on the screen that says "This is a virtue question, play it cool." If you fail a lot of questions, I wouldn't know how to get it back up.

It's all explained here:
http://wiki.ultimacodex.com/wiki/Virtues_in_Ultima_IV#Humility

(the links in the sticky thread are very useful, use them when in doubt)

leave town, enter town, have the conversation again, give the right answer, repeat.
might not even have to leave/enter town.
it's 5 humility points each time.