In the current scanning system all anomalies are divided into bands with each band having its own base signal strength. A list of bands and signal strengths is available on this EVE wiki page.
The lowest base signal strength, and consequentially most difficult to scan down, anomalies have a base signal strength of 1.25%. Thus according to this guide (and allowing for the skill changes in Odyssey) and assuming an 8-probe formation you need a probe sensor strength of at least 68.59 in order to be able to scan them down at all.
The easiest way to get to this level of scan strength on an unbonused ship is to have a combined total of at least 6 levels in Astrometrics and Astrometric Rangefinding, fit 2 gravity capacitor rigs to your ship and use sisters core scanner probes in a T1 core probe launcher.
Of course this is just the minimum level required to have any chance of completely scanning down any anomaly, better skills and equipment will give you more leeway with probe positioning and range, allowing you to scan faster.