The prior ACA route thru N.Dakota/Montana ran e/w mostly on US 2 (seems as though it changed maybe/estimating 5 years ago?) such that it, now, dog-legs n/w-s/e between Glasglow and Dickinson (then e/w on I-94).
I toured on said prior route which included the towns you mentioned Minot & Cutbank - see the old ACA Map Coded BC-1123-07 - you may be able to purchase this older map via the "Classifieds" section of this forum.
Relevant to your camp sites question: Along said prior route there were, at that time/summer 2009, camping locations about every 40 miles. Vacancies at motels were getting really tight due to the oil/gas boom, but camp sites still had plenty of openings late in the afternoon with no reservations.
One added observation - I loved the wide shoulders on US 2. I even went parallel on US 2 off the ACA route between Minot and Williston/fyi.
Regarding 'prevailing winds:' You have probably seen the 'prevailing wind patterns' for that area reported on the internet. Those patterns are nice for 'the averages' I suppose. Even though I traveled west to east I had at least two days in July where the winds were steadily over 28mph east to west, such that I just stopped and waited till the winds did the same :- ). I usually experienced that which you did - winds out of the north.
- Wishing you a great tour.