I haven't used Visio for a few years but I did use it a ton in 1999-2000, sometimes for IA. I'm using OmniGraffle Pro 4 right now for IA.
I've never used Axure RT but it looks decent; I viewed one of their demos and it looks like their scripted UI functionality is deeper than OmniGraffle's, or at least easier to do fancy stuff. OmniGraffle can do inter-document links, open files, run an AppleScript, etc. but it looks like Axure RT has more of a menu-driven model for creating elaborate stuff.
As for OmniGraffle Pro 4 vs. Visio 2000 (the only Visio comparison I can make), IMO it is in every way nicer to use, less buggy, less aggravating than Visio. If you've used Visio you know exactly what I mean when I say that it's aggravating - lots of rough edges, having to do things over and over to try and get it to do what you want, etc. OmniGraffle is much more polished and sane.
OG for IA: A stencil is provided for Jesse James Garett's IA vocabulary which is good for site maps. I'm also using a stencil I downloaded from Michael Angeles' site
for individual wireframe elements. BTW stencils are trivial to make since they're just plain old OmniGraffle documents in a specific folder. So, I've made a few elements of my own and put them in a stencil.
I'm very happy with OmniGraffle for IA, and mainly that's because it's a really good general diagramming tool. I don't want a specialized IA tool with advanced interactivity or requirements exporting like Axure RT (its generated requirements documents look pretty pointless to me) so OmniGraffle is a really good fit. From what I've seen, it's also becoming something of a de facto standard among Mac based IA's, so there are several sites with general advice that also provide OmniGraffle samples and/or stencils alongside the Visio versions.
I should add that if I were working on a project with very poor definition of design direction that needed lots of stakeholder or end user feedback, I might lean toward a tool that helped me build hi-fi prototypes such as Axure RT or maybe Ruby on Rails, and skip the site map / wireframe step altogether. As it is I am working on a small team with very strong internal design leadership so it's more efficient to work in wireframe land and defer pretty prototypes and implementation until later.