Indeed, there always should be a server-side fallback.
I haven't seen a browser that its JS is turned off
You wouldn't see it unless you were looking over the shoulders of all your site users. People have the option to turn off JS in their browser. But that's not the whole issue. They may be using a browser with poor JS support, or a browser plugin might be messing with your script etc. So JS can fail as well as be off. You just can't rely on it, because you can't control it.
JS should be thought of as an enhancement rather than a dependancy—at least, as much as possible. So your server side script is essential, but client side validation is a nice enhancement for those who can access it or who want it.