We installed vault on our server due to jobs now requiring it but when we did, we had a huge increase in cpu usage when players were doing things like mining. The more players mining, the worse the lag got. Removing this plugin would make the lag go away. Any idea why this would be happening?

Here is my plugin list.
ColorMe 3.4.1
HawkEye 1.0.6
Websend 1.3
obuShutTheHellUp 0.3
bShortcut 1.2.1
Essentials 2.8.3
mcore2 1.0.0
PorteCoulissante 1.2.8
SimpleSpleef 3.0.10
NoFarm 0.3.5
ShowCaseStandalone 0.72
EssentialsChat 2.8.3
Jobs 2.6.3
vampire 4.3.2
HomeSpawnPlus 1.4.3
BKCommonLib 1.15
NoLaggExamine 1.02
Lift 9
Residence 2.5.5
FoundDiamonds 3.1.1
Vanilla 0.2
StopTalkingAutoBan 2.0.4
dynmap 0.35-991
CommandSigns 1.3.0
Votifier 1.6
PermissionsBukkit 1.6
VanishNoPacket 3.3
Lockette 1.5
BanRecipe 1.0
mcMMO 1.3.02-b412
Multiverse-Core 2.4-b521
WorldEdit 5.3-SNAPSHOT
MoreMinecartStarter 1.3.1
Anti Enderman 1.1
BorderGuard 4.31
LagMeter 1.7
Factions 1.6.7
OpenInv 1.8.3
BOSEconomy 0.7.3.1
PearlXP 1.2
Buycraft 3.9
SpawnMob 2.1.0
MobDisguise 1.8
TimTheEnchanter 2.0
NoCheat 3.4.3
Superpickaxe 0.4e
ServerSave 1.4
JSONAPI 3.4.5
AutoMessage 1.5

We are running 1.2.4 r-01 right now but this issue was also happening with 1.2.3. Any help would be appreciated. There are no log errors being generated, just a maxed out cpu usage caused by mining and things like that.

nope, it's not vault causing the issue regardless of if Vault increases lag on your server when it's installed. Vault is a passive interface that allows plugisn to hook into it. Most likely lag resulting from someone doing something improperly with Vault itself. I'd debug against removing other plugins not Vault.

Bukkit should have debugging methods now to tell you what plugins are using the most CPU, I'd start there.