Estoy viendo que en el CORDE aparecen unos cuantos casos de advogado (o aduogado) y derivados, como este:

Y el Rey solamente remitió mil ducados al advogado fiscal para gastos criminales, con tantas piguilas, que apenas se hizo alguno dellos.

Luis Cabrera de Córdoba, "Historia de Felipe II, rey de España", c1619 (España).

No hay casos mucho más allá, siendo el más reciente que encuentro de 1625. Estos casos coinciden en el tiempo con los casos de avogado, sin la d, como el siguiente:

El emperador escogió y nombró para juezes de possessión al licenciado Acuña [...]; hizo avogado al licenciado Juan Rodríguez de Pisa, fiscal al doctor Ribera, y secretario a Bartholomé Ruyz de Castañeda.

Francisco López de Gómara, "La primera parte de la Historia natural de las Indias", 1554 (España).

Los casos de avogado no van más allá de 1626, aunque hay uno de auogado de 1705:

En la ziudad de Burgos a veinte y seis de octubre, año de mil setezientos y zinco, el señor lizenziado don Francisco López de Murillas, auogado de los Reales Consejos, theniente de correxidor desta ziudad y su xurisdicción por Su Magestad [...].

Anónimo, "Acta de 29-X-1705 [Documentos de teatro en Burgos (1700-1752)]", 1705 (España).

En ambos casos el número total de ejemplos encontrados no van más allá de unas cuantas docenas. En cambio, si buscas abogado salen miles de ejemplos incluso limitando la búsqueda a textos anteriores a 1600. Ejemplo:

E demás, dióles Spíritu Santo por abogado que los lenguajes que non entendiesen nin sabíen fablar, que ge los feziese entender e saber.

Alfonso X, "Setenario", c1252-1270 (España).

O este que parece más claro, también del siglo XIII:

Preguntaron a Martín Alfonso que por qué lo mandara desafiar, dixo Pero Lopes de Fontecha, que era abogado de Martín Alfonso, que non auýa ya por qué lo dezir, que muchas cosas le pudiera fazer porque le sería vergüença de las dezir, así commo yazerle con la muger o acometerle su cuerpo, mas abasaua asaz que'l tenýa desafiado quando lo mató.

Anónimo, "Libro de los fueros de Castiella", a1284 (España).

Parece poco probable que sean errores de transcripción, dado que el texto pone había como auýa, respetando la u/v de entonces, mientras que sí que pone abogado.

Como nota, también aparece una docena de casos de adbogado, el más reciente de 1679.

Así pues, parece que la forma dominante de la palabra ya en el siglo XIII era abogado, con figuras de la talla de Alfonso X escribiéndolo así. Esto se atestigua, como bien dices, con la entrada de abogado en el diccionario de Nebrija de 1495. Covarrubias en 1611 recoge abogado, abogar y abogacía.

El verbo abogar se usaba (y usa) como:

Defender los Abogados en juicio las causas y pleitos, y alegar de la justicia, ù derecho de las partes, que se valen de ellos para este fin.

Sin embargo, existía otro verbo muy similar que significaba otra cosa distinta:

AVOCAR. Llamar ante sí algun Tribunal superior, y traher los autos de alguna causa, citando las partes litigantes, y sacando el processo de otro Tribunal inferior.

Esta venía del latín avocare, aunque también existía advocar que venía de advocare:

ADVOCAR. Llamar hacia sí, atraher, ò mover à alguno.

Con esta información, ¿qué dirías que es un advocado? Parecería que se refiere a alguien que es llamado (atraído o invocado por un tribunal), pero no, el Diccionario de Autoridades dice que es lo mismo que abogado. Confuso, ¿no? ¿Y avocado entonces? Era sencillamente el participio pasado de avocar.

¿Qué dirías que significa la siguiente frase del Vidal Mayor de 1250?

Et otrosí el aduocado deue ser puesto ante l'alcalde, seyendo present el aduersario, o deue ser feito público instrumento al poner del aduocado.
("El advocado debe ser puesto ante el alcalde, estando presente el adversario.")

¿"Advocado" aquí entonces qué es? ¿Abogado o invocado? Pues parece que abogado, y así descubrimos que en los siglos XIII y XIV resulta que advocado era bastante común, al menos en algunos textos donde se habla de advocato procurador (siendo procurador sinónima de abogado defensor).

Así pues, tenemos que en un momento en el que España estaba dividida en reinos, algunos textos usan abogado, otros advogado, otros advocato... alguna tenía que imponerse, y seguramente el hecho de que existía un verbo advocar, que acabó tomando otro significado allá por el siglo XVI, ayudó para que se acabara distinguiendo una palabra de otra, adoptándose la forma con b de abogado.

Nota: la conclusión es una suposición mía. Me faltaría encontrar alguna fuente fiable que lo corrobore. Y claro, faltaría por saber cómo es que en el siglo XIII la forma dominante ya era abogado.