Remember, DVC wasn't Brown's first book using church/church history. Angels & Demons came before. And that wasn't really huge until after DVC, And it was published by a different publisher. How does this work? Wouldn't the Angels & Demons guys want to keep the second book?
If you don't include a guide to dating for women that he wrote under the name Danielle Brown, then DVC was actually Dan Brown's fourth book, after Digital Fortress (1998), Angels and Demons (2000), and Deception Point (2001). None of them did particularly well.
Generally when a writer skips from publishing house to publishing house, it means that their books are not consistently selling or that the newer piece was not as good as the previous one, at least in the eyes of the publishing house. In other words, they decided not to take advantage of their second-book clause, which is a standard clause in the boilerplate publishing contract for any company. It usually goes something like this:
Option. The Author grants Publishing House the exclusive option to acquire the same rights as have been granted in this Agreement to the next full-length work to be written by the Author. Publishing House will be entitled to a period of sixty (60) days after submission of a proposal and sample chapters for the next work in which to make an offer for that work, during which time the Author agrees not to solicit any third-party offers, directly or indirectily. If Publishing House wishes to acquire the next work, the Author and Publishing House will attempt to reach an agreement as to terms during a reasonable period of exclusive negotiations. If they cannot reach an agreement, the Author shall be free to Submit the next work elsewhere, but the Author may not accept an offer from any other publisher on terms equal to or less favorable than those offered by Publishing House.
This means, essentially, that the publishing house has dibs on your next book, but if they don't want it, they don't have to make an offer. If they make an offer and you don't accept it, and you shop it around and no one makes a better offer, then you can't accept a lower offer at another house and you have to go with the original offer at the original house. This protects them from having you jump ship and protects you from having to turn down better offers at other houses because the offer at your house was too low. Generally contracts read like this; they're meant to protect both the interests of the author and of the company, sometimes leaning to one side and sometimes to the other, which is why agents like to negotiate clauses. Most of the time this is not one of those clauses.
Dan Brown's last book before DVC was Deception Point, which was published by Pocket Books, like his previous book, Angels and Demons. For whatever reason, Pocket Books took a look at DVC and said "enough with this guy already" and let him make offers elsewhere. He got a contract with Doubleday, and he took it. I'm going to guess it wasn't much, but he certainly made it up in royalties. Pocket Books has retained the rights to Angels and Demons, and reissued it in 2006, but have also sold the rights to other companies for whatever complex reasons they would have to do that. Man, are those guys kicking themselves.