На oDesk для верификации нужно предоставить копию удостоверяющего личность документа и да, скан счета за коммунальные услуги или выписки с банковского счета.
На Elance для верификации нужно отправить скан удостоверяющего личность документа, после чего Вам будет назначено время, в которое Вам позвонит по Skype сотрудник Elance. В процессе звонка он может попросить показать этот документ в камеру.
И да, работать без верификации можно, никаких ограничений вроде бы нет — по крайней мере, я их не заметил.