"Incorrect padding" can mean not only "missing padding" but also (believe it or not) "incorrect padding".
If suggested "adding padding" methods don't work, try removing some trailing bytes:
lens = len(strg)
lenx = lens - (lens % 4 if lens % 4 else 4)
try:
result = base64.decodestring(strg[:lenx])
except etc
Update: Any fiddling around adding padding or removing possibly bad bytes from the end should be done AFTER removing any whitespace, otherwise length calculations will be upset.
It would be a good idea if you showed us a (short) sample of the data that you need to recover. Edit your question and copy/paste the result of print repr(sample)
.
Update 2: It is possible that the encoding has been done in an url-safe manner. If this is the case, you will be able to see minus and underscore characters in your data, and you should be able to decode it by using base64.b64decode(strg, '-_')
If you can't see minus and underscore characters in your data, but can see plus and slash characters, then you have some other problem, and may need the add-padding or remove-cruft tricks.
If you can see none of minus, underscore, plus and slash in your data, then you need to determine the two alternate characters; they'll be the ones that aren't in [A-Za-z0-9]. Then you'll need to experiment to see which order they need to be used in the 2nd arg of base64.b64decode()
Update 3: If your data is "company confidential":
(a) you should say so up front
(b) we can explore other avenues in understanding the problem, which is highly likely to be related to what characters are used instead of +
and /
in the encoding alphabet, or by other formatting or extraneous characters.
One such avenue would be to examine what non-"standard" characters are in your data, e.g.
from collections import defaultdict
d = defaultdict(int)
import string
s = set(string.ascii_letters + string.digits)
for c in your_data:
if c not in s:
d[c] += 1
print d