This problem is simply a flaw in sh (and its descendants), other shells handle it much better, see for example Tom Duff's rc shell: http://rc.cat-v.org
Also note that Plan 9, the successor to Unix (and which uses the rc shell as its main shell) doesn't even have a find command, find's design is not really very unix-y.
As for your second questions, the answer might be structural regular expressions: http://doc.cat-v.org/bell_labs/structural_regexps/