Du kan starte med at google dem for at se om der klager over dem. Derefter som minimum ville jeg bede om et par referencer og mulighed for at ringe til deres kunder for at høre om de var tilfredse med servicen, og hvilke resultater der var opnået (læs trafik til siden, og endnu bedre konverterende trafik, så man virkeligt kunne måle værdien).
Hvis de har været glade for servicen, så tjek alligevel de links de har i ahrefs.com, da du vil sikre at du får relevante links til din hjemmeside, istedet for trash som splogs eller fra den lokale karateklub.