I would answer your questions as follows: Yes, I think such checks should be returned stamped "Uncollected" not "NSF". No, in my humble opinion, NSF fees should not be assessed on checks returned for uncollected funds.
My bank returns checks for the reason "Uncollected Funds", which is noted in our core software, and our processor (we are outsourced) stamps these checks "Uncollected" and returns them. My bank's policy is to not charge NSF/OD fees if the check is returned for uncollected funds (i.e. the account isn't actually in the negative, but the current collected balance isn't sufficient to cover the funds being drawn by the check).
Of course, to be quite clear, with the customers with accounts marked for "pay on collected funds only", we will still return checks stamped "NSF" and charge them service charges (OD), when/if the account actually goes negative.
Hope this helps.
"Gratitude makes sense of our past, brings peace for today, and creates a vision for tomorrow." - Melody Beattie