Races
This is probably the easiest method of gaining the necessary ability to pop in and out of solid objects: good race choice.
ECL1 [spoiler]Humans (PHB): Humans are actually not as powerful of a race in this situation as some others because they don't get the necessary part of being able to jump into solid objects. However, the extra feat means nabbing Spring Attack is a little less painful.
Dwarf (PHB): Although they don't appear to add anything mechanically, they do have a Con bonus and several abilities that are thematically tied (Stonecunning is a major one). They also have some cool racial options.
Xeph (XPH): Not much going for this race, but their Burst ability is worth bringing up. It's a good boost in movement when it's needed.
Badger Hengoyaki (OA): These were changed to be Humanoid (Shapechanger) in the 3.5 eratta, dropping their LA to 0. The Badger variety has the ability to burrow in both animal and hybrid forms.
Nezumi (OA): These rat-like humanoids don't look like they bring much to the table. However, they are the only LA+0 race I know of that has a 40ft base land speed. This is important once we get to other methods of gaining a burrow speed. Also, the +2 Con doesn't hurt (means they can hold their breath longer)
Asherti (Sand): Also humanoids, Ahserti have a burrow speed as well, albeit only through sand or loose dirt.[/spoiler]
ECL8 [spoiler]
Unbodied (XPH):Incorporealness rocks, and a fly speed means only Flyby Attack is necessary. They are also completely immune to most burrowing monsters (such as Earth Elementals). The fact that they have some manifesting ability doesn't hurt and makes up for the fact their touch attack does crappy damage.
Armand (MM3): Pictured in the OP, these guys have the natural burrow speed as well as good boosts to Dex and Con (no penalty to Str is nice too). Other than that, there isn't much going for them. You don't want to use their defensive stance because you should always be moving.[/spoiler]
Templates[spoiler]
Ghost (MM) LA+5: Incorporeal and undead. You get some nice abilities and tons of immunities. The only reason this isn't blue is because of the hefty LA.
Lycanthropy (MM) LA+2 or +3, varying racial HD: There are several animals that have burrow speeds. These are all good targets for this template. For some serious fun, check out it's sister template the Entomanthrope. An excellent target for that template is the Snow Spider from Frostburn, which gives Spring Attack as a bonus feat as well as Tremorsense, all for low racial HD.
Incorporeality (SS) LA +2: Not really a template per-se, but a transformative ritual deal in Savage Species that gives you the Incorporeal subtype and all the bonuses that come with it. The ability to always dive into any solid object is invaluable and you gain a fly speed, too. Say goodbye to wasting feats on Dodge and Mobility.
Tauric (SS & MM2) LA+2, racial HD: This opens up even more options than Lycanthropy, since Magical Beasts and Vermin are suitable targets as well as animals. For chesse, templates can be stacked onto the bottom part without adding to the LA of the final creature (so long as the creature type of the bottom remains Animal, Vermin, or Magical Beast) Even without, there are lots of options that can make the Mole quite useable (including the aformentioned Snow Spider)
Umbral (SS) LA+5: Gives you undead type and Incorporeal subtype. Replaces any previous attack form with Strength-damaging touch attack and lets you create spawn. An interesting template, but I think the Ghost is better, especially for this LA.
Wraith (SS) LA+7:Undead type and Incorporeal subtype. You gain a faster speed than Umbral and can create spawn as well as having better abilities in the first place. However, the Sunlight Powerlessness is incredibly annoying as it basically means you're useless outside in the day. for LA+7, you can do a lot better.
Mineral Warrior (Und) LA+1:Burrow speed equal to 1/2 base land speed, massive DR, and natural armor boost, +2 Str and +4 Con for only 1 LA? This template is amazing, although the Earth Strike is basically adding your Con to attack 1/day in most cases (since most races you would throw this on have no racial HD)
Necropolitan (LiM) LA+0, lose a level; This isn't really much help, but the fact you no longer have to breathe can make things easier for extended underground stays may make it worthwhile.
Shaodw Creature (LoM) LA+2: The main benefit you're concerned with here is the 1.5 multiplication to all movement modes. This helps a lot, and the other abilities help when you can't burrow.
Dark Creature (ToM) LA+1: Again, the main benefit you're concerned about here is the +10 foot bonus to all speeds, but the other abilities can be helpful too.
Cheesetastic templatesTo be perfectly clear, no sane DM is going to ever allow you to use these unless this game is well into epic (and likely, not even then).
http://www.d20srd.org/srd/epic/monsters/paragonCreature.htm All movement speeds are tripled as a minor benefit of this template.
[urlPseudonatural Creature]http://www.d20srd.org/srd/epic/monsters/pseudonaturalCreature.htm[/url] Double all movement speeds as a minor benefit.
[/spoiler]
(WIP)