Thalias would be great for a pond situation. They reliably come back here every year in a zone 7 (there are 2 species I know of, one is cold tolerant to a zone 6a, the other a zone 7a). They are pond plants (although they can and kind of like to dry off every once and a while). Flowers arent too significant but the leaves are very interesting.
Cannas are good pond plants too (they dont really like being too submerged though).
I really love the look of the black taro elephant ear. Mine bloomed many times last year (But mine goes indoors every winter. They definitely handle frosts with no probelm and even had new growth after low 30s/high 20s. Not a zone 5 plant at all, but maybe it would work well if you heat your pond.
Heating your pond might be a really good idea because then you can grow many nice fish and plants. Remember though that you might need a net to cover it during the winter to keep hungry animals out. During the summer months you might want some motion dection sprinklers or something like it to keep animals out. Digging your pond down to maybe 5 or 6 feet will at least keep your fish from freezing if the heater fails and also give them a chance to swim deep down if an animal threatens. Make sure it has lots of rocks and hiding spots if an animal comes.
Getting a pond with a heater will really expand your plant choices but you can still grow nice plants in cold ponds that dont freeze

Now onto the NON pond plants.
Musa basjoo will make a horrible pond plant because bananas only like moisture on hot days and do like to dry out on days that arent warm. During the winter wet soil will be fatal and they will rot (they can even rot during the summer if given too much moisture. I would keep it dry from first frost on and protect it with heat such as x-mas lights. I protect my palms by wrapping my plants with x-mas lights, wrapping a frost cloth around it, putting a digital thermometer under the frost cloth (to monitor temps from the house), and a plastic garbage bin (to keep heat in and water out. It usually brings temps up about 15-20F but it still might need a little more protection in your zone (I wouldnt let it see below 10F to be safe even though it can handle down to 0F).
Trachycarpus wagnerius is cold tolerant when older, but will need protection to keep it above 10F just to stay alive and above 15F to keep it looking healthy.
Trachycarpus Fortunei (windmill palm), is a bit more cold tolerant. It will need to stay above 15F in its first years, but when established, it can handle down to 10F or 5F with mimimal damage and probably survive 0F). One of mine was sick, but despite that survived in my area with no protection, 3 record snow falls (over a foot of snow each time which is a lot over here) and 14F. It got no damage.
Needle palms are pretty cold tolerant, more cold tolerant than windmill palms, and can handle probably around 0 to -5F realisticly when an adult. It could handle lower for very very brief periods and definitely not every winter, but still very cold tolerant. Some people claim that it can handle -20F but that isnt realistic because it cant see those type of temps without protection unless it is very old, in a good spot, and for a very very brief period of time.
Yucca rostrata should be okay but given protection below -10F. It might get damage, but Im not sure because the ones by me have never gotten cold damage and are in many peoples landscapes (and I dont live in a desert either).
Another nice plant to try would be the eastern prickly pear. This is native to the eastern part of the country from long island (and much farther north as well) into the ohio valley and down to florida. It can survive down to a zone 4 and shouldnt need any protection by you. Mine were in a pot all winter outside and looked a little wrinkled at times, but now has flower buds forming (and it makes giant yellow flowers).
Rhodedendrons are very nice evergreens and pretty cold tolerant. They flower in the spring but look good all year long.
Wisteria is a nice flowering vine that looks pretty tropical considering that it is very cold tolerant. Its considered a weed here, but a nice weed that grows naturally in forests. The blooms hang down from the plant and it would look good on an arbor as long as it is pruned to a good size.
Knockout roses are one of my favoriates. They bloom in my area from now all the way into late november sometimes blooming with a light snow cover. Im not sure how cold tolerant it is, but they should be around as cold tolerant as normal roses.
Ostich ferns would look nice bordering a forest and are native to eastern forests. It is cold tolerant to a zone 2 and loses its leaves in the fall. Around here it regains leaves around mid april and quickly reproduces. They actually get a small trunk on them when older, but nothing very noticable.
There are lots of others you can also grow. Search some of the plants I named to get more info. As for protection for palms, the palms and cycad forum has some people protecting there palms in cold climates.

Good luck!!
-Alex

Thanks for the reply, sorry I didn't get the subscription email notification for some reason.

I actually decided against the moso bamboo I ordered and went with some Phyllostachys atrovaginata. I will have better luck at thicker culms in my zone

I wasted my money on the moso seeds... I wonder how it would do constrained to a pot as a desk plant even though its not technically what it would want.

Great suggestions. I will be staying away from your standard northern garden staples though such as the rhodo's and roses, etc. I want unique and unusual.

I also decided to skip the yucca for right now so I can concentrate on these.

Interesting pond plant suggestions. I've learned SO MUCH reading the last few days and still know nothing.
Ill take your advice and spread the musa's out from the pond a little.

I like the garbage barrel idea for when I winter my plants. Maybe I will get one, cut out the bottom... then pop the top on after so its accessible and fillable easily.

I was attracted to the waggie lately because I have been reading a lot of conflicting information - from what I have seen online people have been starting to thing the waggies are more cold hardy than the fortunei. I hope that stays the case.

Read my mind with the ostrich ferns I just ordered some.
The wisteria actually looks pretty interesting too.

Have you grown musa's? how quick do they outlive their pots? (they aren't going DIRECTLY in the ground this year I would imagine)

Glad I gave you some ideas!
I havent grown musa basjoo, but have grown other musas such as super dwarf cavendish, little prince, dwarf cavendish, & an ice cream banana. The ice cream banana isnt old enough to pup, but all the others pup pretty freely. My dwarf cavendish has 2 pups. I dont expect it to outgrow its pot anytime soon if ever. I think bananas can stay in pots for a pretty good amount of time. I have seen people keep musa basjoos in pretty small pots until they are as tall as 7 or 8 feet, but I suggest they are planted in the ground before that time.

How big is your musa now. You would be surprised at how tall a well established plant can get in one year with heat, sun, and water (when heat and sun is present).

Good luck!
-Alex

Musa's are just plugs that came in the mail last week. I put them in 4 inch pots for now.
I want to make sure I am comfortable with them being big and healthy enough before I put them in the ground. My suspicion is that I will transplant them to a larger pot end of season, and put them in the ground next late spring.

Musa's are just plugs that came in the mail last week. I put them in 4 inch pots for now.
I want to make sure I am comfortable with them being big and healthy enough before I put them in the ground. My suspicion is that I will transplant them to a larger pot end of season, and put them in the ground next late spring.

I think thats a good idea because small plants do need to taken care of until they get to a good size. Once you get a strong stalk and maybe evidence f some pups coming, then its ready to go in the ground.

Wish you luck!