If you're encumbered, riding a horse will allow you to fast-travel. While the horse can't carry anything itself, it does make it a little easier if you're outside and encumbered.
Another idea, once you find the enchantment, is to enchant clothes (they have minimal weight) with "carrying" enchants. This way, if you get enc'dencumbered, you can don on a piece of clothing to help.