위와 같은 방법이면 transaction/lock 없이는 꼬일 수 밖에 없어 보입니다.
효율은 나쁘지만 MyISAM인 경우 테이블 단위 락 하시면 됩니다.

a테이블의 read락을 거신 후에, 작업을 마치시고 락을 해제하면 꼬이는 문제는 해소될 것으로 보입니다.
락과 관련해서는 아래의 URL을 참조해주세요.
http://dev.mysql.com/doc/refman/5.0/en/lock-tables.html

InnoDB등 다른 DB 형식을 쓰신다면 트랜젝션으로 검색해보세요.

첫번째 방법이나 두번째 방법이나 꼬이는 이유는 같습니다.

서로 다른 둘 이상의 유저가 PK값을 확인하는 시점과 실제 값을 적용하는 시점이 겹치기 때문인데요, 사건(?) 경위는 다음과 같습니다.

(정상적으로 동작되려면)
A user : A테이블 MAX값 추출
A user : A테이블 추출 값 기준으로 A테이블 갱신
A user : B테이블 갱신
B user : A테이블 MAX값 추출
B user : A테이블 추출 값 기준으로 A테이블 갱신
B user : B테이블 갱신

(값이 꼬인 경우)
A user : A테이블 MAX값 추출
B user : A테이블 MAX값 추출
A user : A테이블 추출 값 기준으로 A테이블 갱신
B user : A테이블 추출 값 기준으로 A테이블 갱신하려 하나 PK 중복
A user : B테이블 갱신
B user : ----


A, B가 같은 값을 기준으로 +1해서 PK를 쓰려고 하니 B유저는 PK중복으로 데이터 처리를 못하거나 Failover때문에 오버헤드가 걸리게 되겠죠.

http://kr.php.net/manual/en/function.mysql-insert-id.php

php 같은 경우는 mysql_insert_id 함수 등을 사용하면 꼬이는 문제를 피할 듯 한데, 저도 사용해본 적은 없습니다.