I am putting together my design for a pond that is to be primarily a Koi pond, probably in the 4000-5000 gallon range. Will probably grow to a Koi population in the 10-15 range over 2-3 years. Parts of the pond should get several hours of direct sunlight. I'm planning on max depth of between 4-5 ft.

Many have recommended against having any plants in the pond, but many seem to have been successful doing it. Any recommendations out there on successful plant types and strategies for keeping them alive and thriving?

While the koi are young, they will do little damage to the plants so you should be fine at first if you're using small koi. If you start with big koi (or later when they grow), you have a few options. The best, I think, is to build an attached water garden that also serves as a vegetative filter. The water is pumped above the main pond, through the pond full of plants, and into the koi pond. Another option is to buy plant protectors which can protect the plants. Of course, they restrict the plant growth, and I've had various fish and frogs get stuck in them before. A large bullfrog died as a result (drown). Another option is to put up some sort of mesh barrier to keep the large koi in their half of the pond and plants in another. The final option is to just try to have the koi and plants together and see what happens. If there are a lot of plants and few koi, it might just work. Cover the tops of the plant pots with lots of large gravel to reduce rooting by the koi. I only have two koi in my 1800 gallon pond, and they do minimum damage. The raccoons, however, repot plants every day this time of the year.