You'd be insane to put the primary key in a varchar. Mysql is much faster with static width tables. Your main user table should be static width for all the fields.
As opposed to the insanity of storing UUIDs as strings at all? Once you start going into the rabbit hole, you better be prepared to go all the way down.
No doubt. You can store them as INTs! Tho it does get a little hairy dealing with the conversion with MySQL.
Is this true for all storage engines?
It is not true for innodb (default). See my other comments in this thread.