I think it is not a good idea to restrict user from choosing their username combos.
I agree that
johndoe_ looks uglier than
john_doe but that is not a good enough reason.
What you can instead do is, suggest the possible list of usernames once the user fills his first & last name (like twitter). You can omit
johndoe_ from your suggestion list. But you must still allow the user to go ahead with it if he wants to.
Also think about the scenario when
john_doe are all taken. Now the user might have an option of going with
johndoe1. In this case, I think that first two are far better options than the last one :)