The truth is that most people use a custom variation of the A* algorithm. You will see this across the most of the "big guys"(I can't say who they are in a public forum, but I can tell you that you probably use one of them - guaranteed), where the modification of the heuristics is very dependent on the datasets that they use.
You mentioned pgrouting already, which I would consider a "traditional" option. It is good for doing simple routing algorithms and for most problems. It is also easy to use and uses a traditional database at its backend.
Nevertheless, it really depends on the scale and type of problem you are trying to solve and routing is a graph problem.
Once again, the "big guys" usually have a lot of data that is associated with their graph (for example, traffic data, bus routes, walking paths) that affect the routing algorithm. These are known as multi-modal trip planners (where you also have a choice of planning "modes" - no bike paths - only public transit - that kind of thing). You can think how trip planning also becomes a time sensitive issue (i.e if you walk back a few edges back, you will be able to catch the subway that takes you to your destination forward much faster than if you just tried to navigate the edges forward using the lowest cost).
The "big guys" don't store their data in a traditional database per se, they use pre-computed graphs (welcome hadoop/mapreduce clusters!). As you can imagine, these graphs become really big, so knowing how to connect the edges of adjacent graphs can be a challenge.
Anyway, I would recommend you look at some multi-modal routing graph projects:
Graphserver comes to mind. Not a lot of documentation but a lot of pure coding awesomeness (AFAIK, I believe MapQuest uses a variation of this project for some of their routing products).
Another option would be the OpenTripPlanner which has a lot of smart people behind it (including people from graphserver).