="A"&TEXT(NOW(),"yy")&TEXT(NOW(),"mm")&TEXT(A1+1,"0000") would get what you're looking for. In the above, A1=5 and the result is A08110006
Not sure about the verification though - I'd think you'd need to use some VBA for that.
Let them hate - so long as they fear... Lucius Accius